Problem Statement

There are integers with $N$ different values written on a blackboard. The $i$-th value is Ai​ and is written Bi​ 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\le N\le 100$
• 1≤Ai​≤107
• 1≤Bi​≤109
• All Ai​ are distinct.
• All values in input are integers.

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 $2$s and three $3$s, 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 $1$s, you can do the operation twice.