プライム君は枚のカードを使って、とあるゲームをします。
各カードに正整数が書かれており、 番目に書かれている正整数はです。
プライム君は以下の操作を回行うことで、獲得できるスコアを最大化したいです。
まだ選んでいないカードの中からつ選び、そのカードに書かれている数だけ階段をのぼる。
スタートからのぼった段数の総和をとすると、
が素数のとき、スコアを増やす。 そうでないとき、スコアを減らす。
カードに書かれている数はプライム君から見えています。
プライム君が最適に操作を行うことで得られるスコアの最大値を求めてください。
入力はすべて整数である。
得られるスコアの最大値を出力してください。
4 2 4 5 7
3
回目の操作でが書かれたカードを選びます。のぼった段数の総和はになるので、スコアが増えます。
回目の操作でが書かれたカードを選びます。のぼった段数の総和はになるので、スコアが増えます。
回目の操作でが書かれたカードを選びます。のぼった段数の総和はになるので、スコアが増えます。
操作は好きなタイミングで終了できます。操作を回で終えることで最終的なスコアはとなり、これが最大です。
4 4 4 4 4
0
操作を回も行わないほうが良い場合もあります。
3 1 1 1
1
6 4 6 4 6 12 9
4