| Good Bye 2014 |
|---|
| Закончено |
Dohyun управляет продуктовым магазином. Он продает n товаров, пронумерованных целыми числами от 1 до n. i-й (1 ≤ i ≤ n) из них стоит ci долларов, и его покупка добавляет hi единиц счастья. Каждый товар можно держать на прилавке только p единиц времени, пока он не потеряет свежесть. Таким образом, Dohyun выставляет на прилавок i-й товар в момент времени ti, и покупатели могут купить этот товар только во время от ti до ti + (p - 1) включительно. Также покупателям не разрешается покупать один и тот же товар более одного раза.
Я бы хотел посетить продуктовый магазин Dohyun'а и купить некоторые товары для новогодней вечеринки, максимизировав при этом своё счастье. Так как я очень занятой человек, я могу посетить магазин только один раз и очень ненадолго. Иными словами, если я зайду в магазин во время t, то я могу купить только товары, доступные во время t. Но я могу купить произвольное количество товаров, пока их стоимость не превзойдёт мой бюджет. Я не могу купить один и тот же товар более одного раза, согласно правилам магазина. Не требуется расходовать весь бюджет.
Я написал список из q пар целых чисел (aj, bj), что означает, что я могу посетить магазин в момент времени aj, и потратить там не более bj долларов. Для каждой пары я бы хотел знать максимальное достижимое значение счастья по итогам посещения магазина. Но пар так много, что я не могу с ними справиться. Вы можете мне помочь?
В первой строке записано два целых числа через пробел, n и p (1 ≤ n ≤ 4000, 1 ≤ p ≤ 10 000) — количество товаров и время, на протяжении которого товар можно держать на прилавке.
В следующих n строках содержатся описания товаров. В i-й (1 ≤ i ≤ n) из них записано три целых числа через пробел, ci, hi, ti (1 ≤ ci, hi ≤ 4000, 1 ≤ ti ≤ 10 000) — стоимость i-го товара, счастье от покупки i-го товара и время, когда i-ый товар выкладывается на прилавок.
В следующей строке записано целое число q (1 ≤ q ≤ 20 000)— количество вариантов посещения магазина.
В следующих q строках записаны варианты. В j-й (1 ≤ j ≤ q) из них записано два целых числа через пробел aj, bj (1 ≤ aj ≤ 20 000, 1 ≤ bj ≤ 4000) — время посещения магазина и бюджет для j-го посещения.
Для каждого варианта выведите единственную строку, содержащую максимальное количество счастья, достижимое путем покупки некоторых товаров.
4 4
2 3 2
3 5 1
4 7 2
11 15 5
4
1 3
2 5
2 6
5 14
5
8
10
18
5 4
3 2 1
7 4 4
2 1 2
6 3 5
3 2 2
10
1 5
2 5
4 8
4 9
4 10
5 8
5 9
5 10
8 4
7 9
2
3
5
5
6
4
5
6
0
4
Рассмотрим первый пример.
- В момент времени 1 доступен только 2-й товар. Можно купить 2-й товар за 3 доллара и мое счастье возрастет на 5.
- В момент времени 2 доступны 1-й, 2-й и 3-й товары. Я могу купить 1-й товар за 2 доллара и 2-й товар за 3 доллара. Мое счастье возрастет на 3 + 5 = 8.
- В момент времени 2 доступны 1-й, 2-й и 3-й товар. Я могу купить 1-й товар за 2 доллара и 3-й товар за 4 доллара. Моё счастье возрастет на 3 + 7 = 10.
- В момент времени 5 доступны 1-й, 3-й и 4-й товары. Я могу купить 1-й товар за 2 доллара и 4-й товар за 11 долларов. Моё счастье возрастет на 3 + 15 = 18. Обратите внимание, что мне не надо использовать весь бюджет в этом случае.
