롤러코스터 타기

상근이와 친구들이 놀이공원에 놀러 갔다. 이 놀이공원에는 여러 종류의 롤러코스터가 있고, 상근이는 각 롤러코스터를 미리 분석해 두었다. 상근이는 각 롤러코스터를 탔을 때 느끼는 재미를 숫자로 적어 두었다. 하지만 같은 롤러코스터를 여러 번 탈수록 느끼는 재미는 점점 줄어든다.

상근이는 $i$번 롤러코스터를 $k$번째로 탔을 때 느끼는 재미를 다음 함수로 정의했다.

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

만약 $f(i, k)$가 양수가 아니라면, 그 롤러코스터를 더 타도 재미를 전혀 느끼지 못한다.

상근이는 재미의 합이 최대가 되도록 롤러코스터를 타려고 한다. 놀이공원에 머무를 수 있는 시간이 주어질 때, 롤러코스터를 타는 데 든 시간의 합이 그 시간을 넘지 않으면서 얻을 수 있는 재미의 최댓값을 구하면 된다. 각 롤러코스터를 한 번 타는 데에는 정해진 시간이 걸린다.

첫째 줄에 롤러코스터의 개수 $N$이 주어진다. ($0 < N \le 100$)

다음 $N$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $t_i$가 주어진다. $a_i$와 $b_i$는 재미 함수의 계수이고, $t_i$는 $i$번 롤러코스터를 한 번 타는 데 걸리는 시간이다. ($0 \le a_i, b_i \le 1{,}000$, $0 < t_i \le 25{,}000$)

그다음 줄에는 놀이공원을 방문하는 횟수 $Q$가 주어진다. ($0 \le Q \le 1{,}000$)

다음 $Q$개의 줄에는 상근이가 놀이공원에 머무를 수 있는 시간 $T_i$가 각각 주어진다. ($0 \le T_i \le 25{,}000$)

$Q$개의 줄을 출력한다. 각 방문 시간 $T_i$에 대해, 롤러코스터를 타는 데 든 시간의 합이 $T_i$를 넘지 않도록 하면서 상근이가 얻을 수 있는 재미의 최댓값을 한 줄에 출력한다.