おことわり

想定解は Python3 では TLE しますが PyPy3 で提出すれば AC することが確認されています。

問題文

りあんくんは忍者の末裔で、分身をすることが可能です。

今日りあんくんはプログラミングコンテストに参加していて、考察の結果、全ての問題の解法とコーディングにかかる時間がわかりました。ただ、考察に随分時間を使ってしまって、コーディングをする時間があと $T$ 分しか残っていません。

そこで、得意の分身を使って並列にコーディングをすることにしました。ただ、分身するにも人数分PCを用意するにもコストがかかるので、なるべく分身する人数を少なくしたいです。

なので、時間内に全完するのに必要な最少の分身人数（何人で並列にコーディングすれば時間内に全完できるか）を求めてください。

なお、PC間でのコードのコピペをすることができないので、一つの問題は複数のPCで分担せず一台のPCで書き切らなければいけません。

入力

$T$
$N$
$t_1$
:
$t_N$

1行目に、コンテストの残り時間 $T$ が与えられます。

続いて2行目に、問題の数 $N$ が与えられます。

続いて3行目から $N$ 行の間、$i$ 番目の問題の実装にかかる時間 $t_i$ が与えられます。

入力は全て整数で、以下の制約を満たします。

• $1 \le T \le 2000$
• $1 \le N \le 17$
• $1 \le t_i \le T$

出力

時間内に全完するのに必要な最少の分身人数を出力してください。

最後に改行してください。

サンプル

5
3
1
5
3

2

9
4
5
5
5
5

4

10
6
2
2
2
3
5
6

2