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 долларов. Для каждой пары я бы хотел знать максимальное достижимое значение счастья по итогам посещения магазина. Но пар так много, что я не могу с ними справиться. Вы можете мне помочь?
Выходные данные
Для каждого варианта выведите единственную строку, содержащую максимальное количество счастья, достижимое путем покупки некоторых товаров.
Примечание
Рассмотрим первый пример.
- В момент времени 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. Обратите внимание, что мне не надо использовать весь бюджет в этом случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|