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 \textbf{t_i }and fun \textbf{x_i}, which Kate will get if she listen to this song until the end. Right now Kate has exactly \textbf{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. \InputFile The first line contains the number of available songs \textbf{n} (\textbf{0 }≤ \textbf{n} ≤ \textbf{100}). Each of the next \textbf{n} lines contains two integers: \textbf{t_i} (\textbf{1 }≤ \textbf{t_i} ≤ \textbf{1000}) and \textbf{x_i} (\textbf{-1000 }≤ \textbf{x_i} ≤ \textbf{1000}). Then, the number of test cases \textbf{Q} (\textbf{1 }≤ \textbf{Q} ≤ \textbf{10^5}) is specified and each of the following\textbf{ Q} lines contains a single integer \textbf{T} (\textbf{1 }≤ \textbf{T} ≤ \textbf{10^4}). \OutputFile For each query \textbf{Q} in a separate line print the maximum fun that Kate can get.