No.385 Cup Noodle Life
yozaProblem Statement
kruton is in a money crisis this month!
So kruton has decided to eat nothing but cup noodles until the next payday.
At the moment kruton decides on this cup noodle life, his initial money is $M$ yen.
Using that money, he buys as many cup noodles as he likes, of whichever he likes, from cup noodles of $N$ different prices.
Here comes the Broke Chance! When kruton buys a cup noodle, if his remaining money is a prime number, then, mysteriously, he can restore his money to the initial $M$ yen.
However, it seems that a prime number used $1$ time for a Broke Chance can never be used a $2$nd time.
Find the maximum number of cup noodles kruton can buy.
Input
$M$ $N$ $C_1\ C_2\ \dots \ C_N$
Line $1$ contains the initial money $M(1\le M \le 10000)$.
Line $2$ contains the number of kinds of cup noodles $N(1\le N \le 20)$.
Line $3$ contains the prices $C_i(1\le C_i \le 1000, 1\le i \le N)$ of the i-th cup noodle.
Both $M$ and $C_i$ are in yen.
Output
Output the maximum number of cup noodles kruton can buy on 1 line.
Print a newline at the end.
Sample
Sample 1
Input
100 2 47 50
Output
5
If he first buys a $47$-yen cup noodle, his money becomes $53$ yen.
Since $53$ is a prime number, his money returns to $100$ yen.
Next, he buys a $47$-yen cup noodle again, but since $53$ is a prime number already used earlier, his money stays as it is.
Next, if he buys a $50$-yen cup noodle, his money becomes $3$ yen, and since $3$ is a prime number, his money returns to 100 yen.
Finally, if he buys 2 cup noodles at $47$ yen, his money becomes $6$ yen and he cannot buy any more.
Therefore, he can buy at most $5$ cup noodles.
Sample 2
Input
500 5 111 222 333 444 555
Output
8
Sample 3
Input
2447 3 9 6 10
Output
79842
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。