AT_abc263_g [ABC263G] 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$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
3 3
2 4
6 2

输出 #1

3

输入输出样例 #2

输入 #2

1
1 4

输出 #2

2

说明/提示

限制条件

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

样例解释 1

$2+3=5$，$5$ 是素数，因此可以选择 $2$ 和 $3$ 并将其从黑板上擦去。除此之外无法进行其他操作。由于 $2$ 有 $4$ 个，$3$ 有 $3$ 个，所以可以进行 $3$ 次操作。

样例解释 2

$1+1=2$，$2$ 是素数，因此可以选择两个 $1$ 并将其从黑板上擦去。由于 $1$ 有 $4$ 个，所以可以进行 $2$ 次操作。

由 ChatGPT 4.1 翻译