102636: [AtCoder]ABC263 G - Erasing Prime Pairs

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

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.

Input

题意翻译

有 $n$ 种整数 $a_i$ ,第 $i$ 种有 $b_i$ 个。进行若干次操作,每次在这些数中取出两个,若它们的和为质数,分数加一,操作后把这两个数移去,求最大分数。

Output

分数:$600$分

问题描述

黑板上写有$N$个不同的整数。第$i$个值为$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$s和三个$3$s,你可以执行该操作三次。


样例输入 2

1
1 4

样例输出 2

2

我们有$1 + 1 = 2$,且$2$是质数,所以你可以选择$1$和$1$擦除它们。由于有四个$1$s,你可以执行该操作两次。

加入题单

上一题 下一题 算法标签: