Riding Roller Coasters

Sang-geun and his friends went to an amusement park. The park has many kinds of roller coasters, and Sang-geun has analyzed each one in advance, writing down the fun he feels from riding it as a number. However, the more times he rides the same roller coaster, the less fun it becomes.

Sang-geun defined the fun of riding roller coaster $i$ for the $k$-th time as the following function.

$f(i, k) = a_i - (k-1)^2 \cdot b_i$

If $f(i, k)$ is not positive, riding that roller coaster again gives him no fun at all.

Sang-geun wants to ride roller coasters so that the total fun is maximized. Given the amount of time he can stay in the park, find the maximum total fun he can obtain while the total time spent riding roller coasters does not exceed that time. Riding roller coaster $i$ once takes a fixed amount of time.

The first line contains the number of roller coasters $N$. ($0 < N \le 100$)

Each of the next $N$ lines contains three integers $a_i$, $b_i$, and $t_i$. Here $a_i$ and $b_i$ are the coefficients of the fun function, and $t_i$ is the time it takes to ride roller coaster $i$ once. ($0 \le a_i, b_i \le 1{,}000$, $0 < t_i \le 25{,}000$)

The next line contains the number of park visits $Q$. ($0 \le Q \le 1{,}000$)

Each of the next $Q$ lines contains a time $T_i$ that Sang-geun can stay in the park. ($0 \le T_i \le 25{,}000$)

Print $Q$ lines. For each visit time $T_i$, print on one line the maximum total fun Sang-geun can obtain while the total time spent riding roller coasters does not exceed $T_i$.