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