Little Elephant and Colored Coins

All submissions for this problem are available.
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 ith type has the value V_{i} dollars and the color C_{i}. 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 spaceseparated integers V_{i} and C_{i}, denoting the value and the color of the coin of the ith 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
 1 ≤ N ≤ 30
 1 ≤ V_{i} ≤ 200000 (2 * 10^{5})
 1 ≤ C_{i} ≤ 10^{9}
 1 ≤ Q ≤ 200000 (2 * 10^{5})
 1 ≤ S ≤ 10^{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.
Author:  witua 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/LECOINS 
Tags  dynamicprogramming, hard, march13, shortestpath, simplemath, witua 
Date Added:  21032012 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 