Score : $600$ points

问题描述

在黑板上有 $N$ 个不同数值的整数。第 $i$ 个数值是 $A_i$，并且被写了 $B_i$ 次。

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

• 选择黑板上两个整数 $x$ 和 $y$，要求满足 $x+y$ 是质数。擦除这两个整数。

找出该操作最多能执行多少次。

以上为通义千问 qwen-max 翻译，仅供参考。

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 $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.

update @ 2024/3/10 11:08:26