No.5 数字のブロック

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 562
作問者 : yuki2006yuki2006

3 ProblemId : 14 / 出題時の順位表

問題文

Ellenは数字のブロックで遊ぼうとしている。

数字が書かれているブロックはそれぞれ高さ$1$で幅は$W_i$ である。
それらのブロックを高さ1,幅Lの大きな箱の中に入れる。 

Ellenは大きな箱にどれだけブロックがたくさん入るか気になったが。
組み合わせがたくさんあって大変なことに気づいて、すぐに夜になってしまいそうである。

あなたは、代わりに大きな箱に最大何個のブロックが入るかを求めてください。

入力

$L$
$N$
$W_1 W_2 W_3\dots W_N$

1行目は、大きな箱の幅を表す$L (1 \le L \le 10000)$が与えられます。
2行目は、ブロックの数を表す$N(1 \le N \le 10000)$
3行目は、各ブロックの幅を表す$Wi(1 \le Wi \le L )$が半角スペース区切りで与えられます。

出力

求めた数値を返してください。末尾に改行を付けてください。

サンプル

サンプル1
入力
16
3
10 5 7
出力
2

幅16の箱には全部は入れられないが最大2個までは入れられる。

サンプル2
入力
100
10
14 85 77 26 50 45 66 79 10 3
出力
5

14,26,45,10,3 の組み合わせで最大5個になる (どう組み合わせても6個以上は入らない)

提出ページヘ