시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB54181850.000%

문제

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

상근이는 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에 대해서, 상근이가 느낄 수 있는 최대 재미 점수를 출력한다.

예제 입력 1

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

예제 출력 1

88
5
5
7

예제 입력 2

1
100 3 2
5
2
3
4
5
100

예제 출력 2

100
100
197
197
435
W3sicHJvYmxlbV9pZCI6IjM5NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzAgXHVkMGMwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YjE4MFx1Yzc3NCBcdWFjZjVcdWM2ZDBcdWM1ZDAgXHViMTgwXHViN2VjXHVhYzE0XHViMmU0LiBcdWM3NzQgXHViMTgwXHVjNzc0IFx1YWNmNVx1YzZkMFx1YzVkMFx1YjI5NCBcdWI5Y2VcdWM3NDAgXHVjODg1XHViOTU4XHVjNzU4IFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHViODY0XHViN2VjXHVjZjU0XHVjMmE0XHVkMTMwXHViOTdjIFx1YmJmOFx1YjlhYyBcdWJkODRcdWMxMWRcdWQ1NzQgXHVjNjU0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAxIFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1Yjk3YyBcdWQwZDRcdWM3NDQgXHViNTRjIFx1YjI5MFx1YjA4NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzdhY1x1YmJmOFx1Yjk3YyBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjODAxXHVjNWI0XHVjNjU0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1Yjk3YyBcdWQwYzggXHViNTRjIFx1YjljOFx1YjJlNCBcdWIyOTBcdWIwN2NcdWIyOTQgXHVjN2FjXHViYmY4XHViMjk0IFx1YzgxMFx1YzgxMCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBpXHViYzg4IFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1Yjk3YyBrXHViYzg4XHVjOWY4XHViODVjIFx1ZDBkNFx1Yzc0NCBcdWI1NGMgXHViMjkwXHViMDdjXHViMjk0IFx1YzdhY1x1YmJmOFx1Yjk3YyBcdWQ1NjhcdWMyMThcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTc0IFx1YzY1NFx1YjJlNC4gZihpLCBrKSA9IGE8c3ViPmk8XC9zdWI+IC0gKGstMSk8c3VwPjI8XC9zdXA+KmI8c3ViPmk8XC9zdWI+LiBcdWI5Y2NcdWM1N2QgZihpLGspXHVhYzEyXHVjNzc0IFx1YzU5MVx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2NcdWJhNzQsIFx1YWRmOCBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWI5N2MgXHVkMGMwXHViYTc0LCBcdWIzNTRcdWM3NzRcdWMwYzEgXHVjN2FjXHViYmY4XHViOTdjIFx1YjI5MFx1YjA3Y1x1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjN2FjXHViYmY4XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHVhYzhjIFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1Yjk3YyBcdWQwYzBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWIxODBcdWM3NzQgXHVhY2Y1XHVjNmQwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMCAmbHQ7IE4gJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4sIHQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1Yzc4OFx1YjJlNC4gYTxzdWI+aTxcL3N1Yj5cdWM2NDAgYjxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgxNVx1Yzc1OFx1ZDU1YyBcdWQ1NjhcdWMyMThcdWM3NTggXHVhY2M0XHVjMjE4XHVjNzc0XHVhY2UwLCB0PHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4XHVjOWY4IFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1Yjk3YyBcdWQwYzBcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC4gKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwgMCAmbHQ7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMjUsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjE4MFx1Yzc3NCBcdWFjZjVcdWM2ZDBcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWFjMWNcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgUSAmbGU7IDEsMDAwKSBcdWIyZTRcdWM3NGMgUVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjE4MFx1Yzc3NCBcdWFjZjVcdWM2ZDBcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNCBUPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgVDxzdWI+aTxcL3N1Yj4gJmxlOyAyNSwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzJkY1x1YWMwNCBUPHN1Yj5pPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWIyOTBcdWIwODQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjN2FjXHViYmY4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzk1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvbGxlciBjb2FzdGVyIGZ1biIsImRlc2NyaXB0aW9uIjoiPHA+SmltbXkgYW5kIGhpcyBmcmllbmRzIGxpa2UgdG8gdmlzaXQgbGFyZ2UgdGhlbWUgcGFya3MuIEluIHRoZSBjdXJyZW50IHRoZW1lIHBhcmsgdGhlcmUgYXJlIG1hbnkgcm9sbGVyIGNvYXN0ZXJzIHdoaWNoIHRoZW4gYXJlIGNhdGVnb3JpemVkIGJ5IEppbW15LiBIZSBhc3NpZ25zIGEgZnVuIHZhbHVlIHRvIGVhY2ggY29hc3RlcjsgaG93ZXZlciwgdGhlIGZ1biBkZWNyZWFzZXMgd2l0aCBlYWNoIHJ1bi48XC9wPlxyXG5cclxuPHA+TW9yZSBmb3JtYWw6IGZvciBhIHNwZWNpIGZpYyByb2xsZXIgY29hc3RlciBpLCBKaW1teSBhc3NpZ25zIHR3byBmdW4gY29lZmZpY2llbnRzIGFpIGFuZCBiaS4gV2hpbGUgcmlkaW5nIHRoaXMgcm9sbGVyIGNvYXN0ZXIgZm9yIHRoZSBrLXRoIHRpbWUsIEppbW15IGdhaW5zIGEgZnVuIHZhbHVlIG9mIGYoaSwgaykgPSBhaSAtIChrIC0gMSk8c3VwPjI8XC9zdXA+ICZ0aW1lczsgYmkuIElmIGYoaSwgaykgaXMgbm9uLXBvc2l0aXZlLCByaWRpbmcgdGhlIHJvbGxlciBjb2FzdGVyIGlzIG5vIGxvbmdlciBmdW5ueS48XC9wPlxyXG5cclxuPHA+SmltbXkgdHJpZXMgdG8gbWF4aW1pemUgdGhlIHRvdGFsIGZ1biB1bnRpbCBoZSBsZWF2ZXMgdGhlIHBhcmsuIENhbiB5b3UgdGVsbCBKaW1teSBob3cgbXVjaCBmdW4gaGUgY2FuIGdhaW4gZm9yIGEgZ2l2ZW4gdGltZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNpbmdsZSB0ZXN0IGNhc2UuPFwvcD5cclxuXHJcbjxwPlRoZSBmaSByc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOLCB3aGVyZSBOIGlzIHRoZSBhbW91bnQgb2YgZGlmZmVyZW50IHJvbGxlciBjb2FzdGVycyBpbiB0aGUgdGhlbWUgcGFyayAoMCAmbHQ7IE4gJmxlOyAxMDApLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiB0aGUgaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+IGFuZCB0PHN1Yj5pPFwvc3ViPiB3aGVyZSBhPHN1Yj5pPFwvc3ViPiBhbmQgYjxzdWI+aTxcL3N1Yj4gYXJlIHRoZSBmdW4gY29lZmZpY2llbnRzIGFzIHNwZWNpZmkgZWQgYWJvdmUgYW5kIHRpIGlzIHRoZSB0aW1lIGZvciBhIHNpbmdsZSByaWRlIHdpdGggdGhlIGktdGggcm9sbGVyIGNvYXN0ZXIgKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwLCAwICZsZTsgYjxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMDsgMCAmbHQ7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMjUgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgUSBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoYXQgSmltbXkgaXMgdmlzaXRpbmcgdGhlIHBhcmsgKDAgJmxlOyBRICZsZTsgMSAwMDApLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgUSBsaW5lcyBjb250YWlucyBhbiBpbnRlZ3JhbCB0aW1lIFQ8c3ViPmk8XC9zdWI+IHRoYXQgSmltbXkgc3BlbmRzIGR1cmluZyBoaXMgaS10aCB2aXNpdCAoMCAmbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgMjUgMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBvZiB0aGUgUSBwb3NzaWJsZSB0aW1lcywgcHJpbnQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbWF4aW1hbCB0b3RhbCBmdW4gdmFsdWUgaWYgSmltbXkgc3BlbmRzIFQ8c3ViPmk8XC9zdWI+IG1pbnV0ZXMgaW4gdGhlIHRoZW1lIHBhcmsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==