問題一覧 > 通常問題

No.385 カップ麺生活

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 164
作問者 : yozayoza
11 ProblemId : 913 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-07-01 20:34:08

問題文

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。