No.733 分身並列コーディング

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 30
作問者 : りあんりあん / テスター : confconf
5 ProblemId : 1132 / 出題時の順位表

おことわり

想定解は 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$

出力

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

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

サンプル

サンプル1
入力
5
3
1
5
3
出力
2

1番目と3番目の問題を1人目が、2番目の問題を2人目が解くと2人で時間内に全完することができます。

サンプル2
入力
9
4
5
5
5
5
出力
4

一人一問ずつしか解けません。

サンプル3
入力
10
6
2
2
2
3
5
6
出力
2
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。