문제2061--Roller coaster fun

2061: Roller coaster fun

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 102  통과: 16
[제출] [채점기록] [묻고답하기]

문제 설명

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}\dot 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 \le N \leq 100)$.

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 $(0 \leq a_{i} \leq 1000; 0 \leq b_{i}  \leq 1000; 0 \le t_{i} \leq 25000)$. The next line contains a positive integer $Q$ denoting the number of times that Jimmy is visiting the park $(0 \le Q \le 1,000)$. Each of the following $Q$ lines contains an integral time $T_i$ that Jimmy spends during his $i$-th visit $(0 \leq T_i \leq 25,000)$.

출력 설명

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.

입력 예시 Copy

2
5 0 5
7 0 7
4
88
5
6
7

출력 예시 Copy

88
5
5
7

도움

Sample Input 2

1
100 3 2
5
2
3
4
5
100

Sample Output 2

100
100
197
197
435