分数: 600 点
问题陈述
有整数 N 黑板上写着不同的值。的 i-th 值为 A_i 并写为 B_i 次。
您可以尽可能多次地重复以下操作:
- 选择两个整数 x 和 y 写在黑板上,这样 x+y 是素数。删除这两个整数。
查找该操作可以执行的最大次数。
约束
- 1 \leq N \leq 100
- 1 \leq A_i \leq 10^7
- 1 \leq B_i \leq 10^9
- 全部 A_i 是不同的。
- 输入中的所有值都是整数。 您选择的
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
打印答案。
示例输入 1
3 3 3 2 4 6 2
示例输出 1
3
我们有 2 + 3 = 5,和 5 是素数,所以你可以选择 2 和 3 删除它们,但没有别的。由于有四个 2和三 3秒,可进行3次操作。
示例输入 2
1 1 4
示例输出 2
2
我们有 1 + 1 = 2,和 2 是素数,所以你可以选择 1 和 1 删除它们。由于有四个 1s,您可以执行两次操作。