Erasing Prime Pairs

题目描述

黑板上写着 $N$ 个不同值的整数。第 $i$ 个值是 $A_i$，写了 $B_i$ 次。 你可以重复以下操作任意多次：

选择黑板上写着的两个整数 $x$ 和 $y$，使得 $x+y$ 为素数。擦去这两个整数。

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

输入格式

输入按照下列格式由标准输入给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

输出答案。

3
3 3
2 4
6 2

3

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$ 互不相同。 输入中的所有数值均为整数。我们有 $2 + 3 = 5$，且 $5$ 是素数，所以你可以选择 $2$ 和 $3$ 把它们擦去，但别无他法。由于有四个 $2$ 和三个 $3$，你可以执行该操作三次。
我们有 $1 + 1 = 2$，且 $2$ 是素数，所以你可以选择 $1$ 和 $1$ 把它们擦去。由于有四个 $1$，你可以执行该操作两次。

标签: AtCoder|abc263G

来源

AtCoder|abc263G