擦除素数对

题目描述

黑板上写着 $N$ 种整数。第 $i$ 种整数是 $A_i$,写有 $B_i$ 个。

你可以尽可能多地重复以下操作:

• 选择黑板上写的 $2$ 个整数 $x,y$,使得 $x+y$ 是素数。把选中的 $2$ 个整数从黑板上擦掉。

求最多可以执行多少次操作。

输入格式

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

输出答案。

样例

3
3 3
2 4
6 2

3

因为 $2 + 3 = 5$,而 $5$ 是素数,所以可以选择 $2$ 和 $3$ 擦除。除此之外没有其他可执行的操作。由于 $2$ 有 $4$ 个、$3$ 有 $3$ 个,所以最多可以执行操作 $3$ 次。

1
1 4

2

因为 $1+ 1 = 2$,而 $2$ 是素数,所以可以选择 $1$ 和 $1$ 擦除。由于 $1$ 有 $4$ 个,所以最多可以执行操作 $2$ 次。

数据范围

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 10^7$
• $1 \leq B_i \leq 10^9$
• 所有 $A_i$ 互不相同。
• 所有输入都是整数。