스탠딩 데스크

Anna의 엄마는 Anna가 매일 컴퓨터 앞에 너무 오래 앉아 있다고 불평한다. 이 문제는 Anna가 반드시 해결할 것이다. Anna는 컴퓨터 앞에서 대신 서 있기로 결심했다!

하지만 컴퓨터 모니터가 너무 높은 곳에 있다! 인체 공학적인 이유로 Anna는 정확히 $x$센티미터 높아져야 한다. Anna에게는 이를 위해 사용할 수 있는 $n$개의 판이 있다. 각 발 아래에 판을 몇 개씩 놓으면 정확히 $x$센티미터 높아질 수 있다. 따라서 오른발 아래에 놓인 판들의 높이 합은 $x$센티미터여야 하며, 왼발 아래에 놓인 판들의 높이 합도 $x$센티미터여야 한다. Anna에게 필요한 판의 총개수의 최솟값은 얼마인가?

첫째 줄에 수 $x$와 $n$가 주어진다($10 \leq x \leq 100$, $2 \leq n \leq 20$). 이들은 각각 Anna가 각 발 아래에 추가해야 하는 높이의 센티미터 수와 판의 개수를 나타낸다.

그다음 줄에 $n$개의 정수 $h_i$가 주어진다($1 \leq h_i \leq 100$). 항상 해가 존재한다.

정답을 추측하기 어렵게 하기 위해 두 정수 $n_1$와 $n_2$를 출력한다. 이는 Anna가 각 발 아래에 놓는 판의 개수이다. 더 작은 수를 먼저 출력한다. 즉, $n_1\leq n_2$가 성립하도록 한다. 판의 총개수가 같은 해가 여러 개라면 그중 어느 것이든 선택할 수 있다.

그룹 | 배점 | 제한

$1$ |$30$| $n \leq 12$

$2$ |$70$| 추가 제한 없음.