← 返回题目列表

AtCoder · abc263_g

G. 删除素数对

中文机器翻译题面 查看原题

分数: 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,您可以执行两次操作。