Listen to the song (Hard)#4364
Fikret the anteater settled into one of the social networks. But he speaks rather peculiarly. Instead of compliments, and other things, he sends songs to his beloved echidna Kate. They have been friends for a long time, so Fikret masterfully understands her musical preferences. For each song are known three characteristics: duration t_i, fun x_i, which Kate will get if she listens to this song until the end and value y_i, which will reduce the fun of the song every time Kate listens to it. That is, if at the moment fun of the song equals , then the second time Kate listens to this song (not necessarily consecutive), fun will be equal to (x-y), at the third (x-y-y)...
Right now Kate has exactly 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 happens automatically and without interruption.
The first line contains the number of available songs (0 \le n \le 100). Each of the next lines contains three integers: t_i (1 \le t_i \le 100), x_i (-100 \le x_i \le 100), y_i (-100 \le y_i \le 100). Then, the number of test cases (1 \le Q \le 10^5) is specified and each of the following lines contains a single integer (1 \le T \le 100).
For each query in a separate line print the maximum fun that Kate can get.
Example 1