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 three characteristics: duration \textbf{t_i}, fun \textbf{x_i}, which Kate will get if she listen to this song until the end and value \textbf{y_i}, which will reduce the fun of the song every time Kate listen to it. That is, if at the moment fun of the song equals \textbf{x}, then at the second time Kate listen to this song (not necessarily consecutive), fun will be equal to \textbf{(x-y)}, at the third \textbf{(x-y-y)}... 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 three integers: \textbf{t_i} (\textbf{1 }≤ \textbf{t_i} ≤ \textbf{100}), \textbf{x_i} (\textbf{-100 }≤ \textbf{x_i} ≤ \textbf{100}), \textbf{y_i} (\textbf{-100 }≤ \textbf{y_i} ≤ \textbf{100}). 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{100}). \OutputFile For each query \textbf{Q} in a separate line print the maximum fun that Kate can get.