spoj#HEADBANG. Best Saved For The Last
Best Saved For The Last
Mirza is a fresher of IUT(International University Of Technology). Today is his fresher's reception day. His senior brother's arranged an amazing function on that occasion. N best music bands of the country came to perform in his campuss. As per sunset rules, they had to shorten the timespan of the program. So, all the N bands are performing in different auditoriams at the same time. After each song of each band there is a break , when if you wish you can go from one auditorium to other, but not inbetween the songs. And also you want to enjoy the most.
Now, there is a fun value for each song played by each band. When you are listening to a band for the first time, you'll enjoy the most. Then if you hear a song for the second time you'll enjoy less. The value will decrease by times.
More formal: for a specific band i, There is two fun coefficients ai and bi . While listening a song of a perticular band for the k-th time, Mirza gains a enjoyment value of f(i, k) = ai − (k − 1)2 * bi . If f(i, k) is non-positive, listening a song to that band is no longer enjoyable. Note:[If you enjoyed 1st song of a band then go to other auditorum and miss the second song of this band and come back again for the 3rd song, the 3rd song of this band will count as 2nd for you as you are listening them for the 2nd time]
Given the maximum time Mirza can spent in the auditoriums, can you tell the maximum enjoyment value of Mirza.
Input
The first line contains the integer N, where N is the number of band came to perform (0 < N ≤ 100). The following N lines contain the integers ai , bi and ti where ai and bi are the fun coefficients as specified above and ti is the length of each song played by the i-th band (0 ≤ ai ≤ 2500; 0 ≤ bi ≤ 2500; 0 < ti ≤ 50000). The next line contains a positive integer Q denoting the number of Query (0 ≤ Q ≤ 1000). Each of the following Q lines contains an integral time T that Mirza spends in auditorium his (0 ≤ T ≤ 50000).
Output
For each query, Print an integer denotion the maximim enjoyment value Mirza can get.
Example
Input:
2
5 0 5
7 0 7
4
88
5
6
7</p>Output:
88
5
5
7
Input:1100 3 252345100Output:100100197197435