Фабрика производит однодневные дырявые кастрюли. Обычно за один день производится a кастрюль, но сейчас часть оборудования, делающего дырки, сломалась, поэтому производство упало до b кастрюль в день. Руководство фабрики собирается выбрать k последовательных дней и произвести ремонт оборудования. Во время ремонта фабрика не будет ничего производить, зато после его окончания вернётся к производству a кастрюль в день.
Изначально у фабрики нет никаких заказов. Запросы di, ai означают, что ai новых заказов поступило на день di. Для каждого заказа требуется ровно одна однодневная дырявая кастрюля, и, разумеется, она должна быть произведена ровно в этот день (на следующий день кастрюля уже выходит из строя). Фабрика может каждый день удовлетворить любое количество заказов, не превосходящее её производственные мощности для этого дня.
Также в некоторые моменты времени владелец фабрики хочет для некоторого pi знать максимальное количество заказов, которое может быть удовлетворено, если ремонт фабрики будет произведён в дни pi, pi + 1, ..., pi + k - 1.
Выходные данные
Для каждого запроса второго типа выведите максимальное количество заказов, которые могут быть выполнены.
Примечание
Рассмотрим первый пример.
Фабрика производит не больше 1 однодневной дырявой кастрюли в день и будет производить 2 после ремонта. Ремонт занимает 2 дня.
Для первого запроса мы можем выполнить 1 заказ в день 1, 0 заказов в дни 2 и 3, поскольку будет производиться ремонт, 0 заказов в день 4, поскольку ни одна кастрюля не была заказана на этот день, и 2 заказа в день 5, поскольку больше чем 2 кастрюли в день фабрика произвести не может. Таким образом, будут выполнены 3 заказа.
В третьем запросе мы можем выполнить 1 заказ в день 1, 1 заказ в день 2 и 2 заказа в день 5. В итоге будут выполнены 4 заказа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 2 1 8
1 1 2
1 5 3
1 2 1
2 2
1 4 2
1 3 2
2 1
2 3
|
3
6
4
|
|
2
|
5 4 10 1 6
1 1 5
1 5 5
1 3 2
1 5 2
2 1
2 2
|
7
1
|