No.385 カップ麺生活

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 120
作問者 : yozayoza
8 ProblemId : 913 / 出題時の順位表

問題文

kruton君は今月お金がピーンチ!
そこでkruton君は次の給料日までカップ麺のみで食事を済ますことにしました。

kruton君がカップ麺生活を決意した時点での初期所持金は$M$円
その所持金を使って$N$種類の価格のカップ麺から好きなものを好きなだけ購入します。
ここで金欠チャンス! kruton君がカップ麺を購入したときにもし残り所持金が素数である場合、不思議な事に所持金を初期所持金の$M$円まで元通りにすることができます。
ただし、$1$度金欠チャンスで使用した素数は$2$度と使うことが出来ないようです。

このときkruton君が購入することの出来るカップ麺の最大数を求めよ。

入力

$M$
$N$
$C_1\ C_2\ \dots \ C_N$

$1$行目に初期所持金$M(1\le M \le 10000)$が与えられます。
$2$行目にカップ麺の種類の数$N(1\le N \le 20)$が与えられます。
$3$行目にi番目のカップ麺の価格$C_i(1\le C_i \le 1000, 1\le i \le N)$が与えられます。
$M$と$C_i$の単位はどちらも円とします。

出力

kruton君が購入することの出来るカップ麺の最大数を1行で出力せよ。
最後に改行してください。

サンプル

サンプル1
入力
100
2
47 50
出力
5

最初に$47$円のカップ麺を購入すると所持金が$53$円になります。
$53$は素数なので所持金が$100$円に戻ります。
次にまた$47$円のカップ麺を購入しますが$53$は先程使用した素数なので所持金はそのままです。
次に$50$円のカップ麺を買うと所持金が$3$円になって、$3$は素数なので所持金は100円に戻ります。
最後に$47$円のカップ麺を2つ買うと所持金が$6$円になってこれ以上買うことができなくなります。
よってカップ麺を最大$5$個買うことが出来ます。

サンプル2
入力
500
5
111 222 333 444 555
出力
8

サンプル3
入力
2447
3
9 6 10
出力
79842

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

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