题目描述

You are playing a new solitaire game called Prime Time. You are given a deck of cards, and each card has a prime number written on it. Multiple cards may have the same number.

Your goal is to divide the cards into two groups in such a way that the sum of the numbers in the first group is equal to the product of the numbers in the second group. Each card must belong to exactly one of the two groups, and each group must contain at least one card. The sum or product of a group that consists of a single card is simply the number on that card.

For example, in the image above, the left group has cards whose sum is $25$ and the right group has cards whose product is $25$. Therefore, this is a valid split into groups.

Your score is the sum of the numbers in the first group (which is equal to the product of the numbers in the second group), or $0$ if you cannot split the cards this way at all. What is the maximum score you can achieve?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains a single integer $\mathbf{M}$, representing the number of distinct prime numbers in your deck. Each of the next $\mathbf{M}$ lines contains two values: $\mathbf{P}_i$ and $\mathbf{N}_i$, representing that you have exactly $\mathbf{N}_i$ cards with the prime $\mathbf{P}_i$ written on them.

Note that the total number of cards in your deck is the sum of all $\mathbf{N}_i$s.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the maximum score you can achieve.

4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7

Case #1: 25
Case #2: 17
Case #3: 0
Case #4: 8

提示

Sample Explanation

In Sample Case #1, the optimal split is: $11 + 2 + 7 + 3 + 2 = 5 \cdot 5$. Another split is also possible: $5 + 7 + 3 + 2 + 5 = 11 \cdot 2$, but it gives a lower score.

In Sample Case #2, note that cards with the same number can be placed in different groups.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $1 \leq \mathbf{M} \leq 95$. (Note that there are exactly 95 distinct primes between 2 and 499)
• $2 \leq \mathbf{P}_i \leq 499$, for all $i$.
• Each $\mathbf{P}_i$ is prime.
• $\mathbf{P}_i < \mathbf{P}_{i+1}$, for all $i$. (The primes are given in strictly increasing order)
• $1 \leq \mathbf{N}_i$, for all $i$.

Test Set 1 (7 Pts, Visible Verdict)

• $2 \leq \mathbf{N}_1 + \mathbf{N}_2 + \cdots + \mathbf{N}_\mathbf{M} \leq 10$.

Test Set 2 (13 Pts, Visible Verdict)

• $2 \leq \mathbf{N}_1 + \mathbf{N}_2 + \cdots + \mathbf{N}_\mathbf{M} \leq 100$.

Test Set 3 (15 Pts, Hidden Verdict)

• $2 \leq \mathbf{N}_1 + \mathbf{N}_2 + \cdots + \mathbf{N}_\mathbf{M} \leq 10^{15}$.