eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Roller coaster fun

Roller coaster fun

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Jimmy and his friends like to visit large theme parks. In the current theme park there are many roller coasters which then are categorized by Jimmy. He assigns a fun value to each coaster; however, the fun decreases with each run.

More formal: for a specific roller coaster i, Jimmy assigns two fun coefficients a_i and b_i. While riding this roller coaster for the k-th time, Jimmy gains a fun value of f(i, k) = a_i-(k-1)^2·b_i. If f(i, k) is non-positive, riding the roller coaster is no longer funny.

Jimmy tries to maximize the total fun until he leaves the park. Can you tell Jimmy how much fun he can gain for a given time?

Вхідні дані

The input consists of a single test case.

The first line contains the integer N, where N is the amount of different roller coasters in the theme park (0 < N100).

The following N lines contain the integers a_i, b_i and t_i where a_i and b_i are the fun coefficients as specified above and t_i is the time for a single ride with the i-th roller coaster (0a_i1000; 0b_i1000; 0 < t_i25000).

The next line contains a positive integer Q denoting the number of times that Jimmy is visiting the park (0Q1000). Each of the following Q lines contains an integral time T_i that Jimmy spends during his i-th visit (0T_i25000).

Вихідні дані

For each of the Q possible times, print one line containing the maximal total fun value if Jimmy spends T_i minutes in the theme park.

Приклад

Вхідні дані #1
2
5 0 5
7 0 7
4
88
5
6
7
Вихідні дані #1
88
5
5
7
Джерело ACM ICPC German Collegiate Programming Contest 2012