시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 6 6 42.857%

문제

상근이와 친구들은 놀이 공원에 놀러갔다. 이 놀이 공원에는 많은 종류의 롤러코스터가 있고, 상근이는 각 롤러코스터를 미리 분석해 왔다. 상근이는 각 롤러코스터를 탔을 때 느낄 수 있는 재미를 숫자로 적어왔다. 하지만, 롤러코스터를 탈 때 마다 느끼는 재미는 점점 떨어진다.

상근이는 i번 롤러코스터를 k번째로 탔을 때 느끼는 재미를 함수로 정의해 왔다. f(i, k) = ai - (k-1)2*bi. 만약 f(i,k)값이 양수가 아니라면, 그 롤러코스터를 타면, 더이상 재미를 느끼지 않는 것이다.

상근이는 재미의 합이 최대가 되게 롤러코스터를 타려고 한다.

입력

첫째 줄에 N이 주어진다. N은 놀이 공원에 있는 롤러코스터의 개수이다. (0 < N ≤ 100)

다음 N개의 줄에는 ai, bi, ti가 있다. ai와 bi는 상근이가 정의한 함수의 계수이고, ti는 i번째 롤러코스터를 타는데 걸리는 시간이다. (0 ≤ ai, bi ≤ 1,000, 0 < ti ≤ 25,000)

다음 줄에는 놀이 공원을 방문하는 시간의 개수 Q가 주어진다. (0 ≤ Q ≤ 1,000) 다음 Q개 줄에는 상근이가 놀이 공원에 방문하는 시간 Ti가 주어진다. (0 ≤ Ti ≤ 25,000)

출력

출력은 Q개의 줄을 출력한다. 각각의 시간 Ti에 대해서, 상근이가 느낄 수 있는 최대 재미 점수를 출력한다.

예제 입력

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

예제 출력

88
5
5
7

힌트