Fikret-anteater settled into one of the social networks. But he speaks rather peculiar. Instead of compliments, and other things, he sends songs to his beloved echidna Kate. They have long been familiar, so Fikret masterly understands her musical preferences. For each song are known two characteristics: duration t_i and fun x_i, which Kate will get if she listen to this song until the end.
Right now Kate has exactly T units of free time. Knowing the list of available Fikret’s songs, calculate the maximum fun that Kate can get. No two or more songs can play at the same time. Switching between songs is automatically and without interruption.
The first line contains the number of available songs n (0 ≤ n ≤ 100). Each of the next n lines contains two integers: t_i (1 ≤ t_i ≤ 1000) and x_i (-1000 ≤ x_i ≤ 1000). Then, the number of test cases Q (1 ≤ Q ≤ 10^5) is specified and each of the following Q lines contains a single integer T (1 ≤ T ≤ 10^4).
For each query Q in a separate line print the maximum fun that Kate can get.