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