G - Erasing Prime Pairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

黒板に N 種類の整数が書かれています。 i 種類目の整数は A_i で、書かれている個数は B_i 個です。

あなたは次の操作を可能な限り繰り返すことができます。

  • 黒板に書かれている 2 個の整数 x,y であって、x+y が素数であるものを選ぶ。 選んだ 2 個の整数を黒板から消す。

操作を最大で何回行えるか求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^7
  • 1 \leq B_i \leq 10^9
  • A_i は全て異なる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N 
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ。

入力例 1

3
3 3
2 4
6 2

出力例 1

3

2 + 3 = 5 であり、5 は素数なので、2 と 3 を選んで消す操作が行えます。また、それ以外の操作は行えません。 2 は 4 個、 3 は 3 個あるので、操作を 3 回行うことができます。

入力例 2

1
1 4

出力例 2

2

1+ 1 = 2 であり、2 は素数なので、1 と 1 を選んで消す操作が行えます。1 は 4 個あるので、操作を 2 回行うことができます。

Score : 600 points

Problem Statement

There are integers with N different values written on a blackboard. The i-th value is A_i and is written B_i times.

You may repeat the following operation as many times as possible:

  • Choose two integers x and y written on the blackboard such that x+y is prime. Erase these two integers.

Find the maximum number of times the operation can be performed.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^7
  • 1 \leq B_i \leq 10^9
  • All A_i are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N 
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer.

Sample Input 1

3
3 3
2 4
6 2

Sample Output 1

3

We have 2 + 3 = 5, and 5 is prime, so you can choose 2 and 3 to erase them, but nothing else. Since there are four 2s and three 3s, you can do the operation three times.

Sample Input 2

1
1 4

Sample Output 2

2

We have 1 + 1 = 2, and 2 is prime, so you can choose 1 and 1 to erase them. Since there are four 1s, you can do the operation twice.