# CodeChef-LECOINS Little Elephant and Colored Coins 题解

OI

Published

November 18, 2020

Modified

November 18, 2020

CodeChef-LECOINS Little Elephant and Colored Coins

Little Elephant and Colored Coins

The Little Elephant from the Zoo of Lviv very likes coins. But most of all he likes colored coins.

He has N types of coins, numbered from 1 to N, inclusive. The coin of the i-th type has the value Vi dollars and the color Ci. Note that he has infinite supply of each type of coins.

The Little Elephant wants to make exactly S dollars using the coins. What is the maximal number of different colors he can use to make exactly S dollars using some of the coins he has? If it’s impossible, output -1. Also note that the Little Elephant wants to know this for many values of S.

Input

The first line of the input contains a single integer N, denoting the number of types of coins. Each of the following N lines contains two space-separated integers Vi and Ci, denoting the value and the color of the coin of the i-th type. The next line contains a single integer Q, denoting the number of values of S to process. Each of the following Q lines contains a single integer S, denoting the coinage you should represent via given coins using maximum number of colors.

Output

For each value of S in the input, output the maximum number of different colors in the representation of S or -1 if it is impossible to represent S via given coins.

Constraints

• 1N30
• 1Vi200000 (2 * 10^5)
• 1Ci10^9
• 1Q200000 (2 * 10^5)
• 1S10^18

Example

Input:
3
2 1
3 4
4 4
4
1
3
5
7
Output:
-1
1
2
2

Explanation

• It is not possible to represent S = 1 since every coin has value more than 1.
• S = 3 can only be represented using one coin of the second type, hence only one color is used in the representation.
• S = 5 can only be represented as 2 + 3, which leads to two colors used.
• For S = 7 we have two representations as 2 + 2 + 3 (with two colors used) and 3 + 4 (with one color used). Hence, the answer is 2.

## 可达性

$\mathrm{relax} \ f_{(x+V_i)\% V_1} \ \mathrm{by} \ f_x + V_i$

$$\%$$ 代表取模， $$\mathrm{relax} \ A \ \mathrm{by} \ B$$$$A = \min(A,B)$$