Как известно, лучшее украшение клумбы в королевстве Sweetland — ванильные кексики. Процесс их выращивания весьма сложен и требует немалых ресурсов. У Сластены есть m саженцев, и для превращения j-го саженца кексика в произведение искусства необходимо держать его под солнцем не менее kj минут.
Большую часть времени в Sweetland стоит прекрасная погода, которая лишь иногда омрачается появлением карамельных облаков, i-е из которых возникает в момент времени (минуту) li и исчезает в момент времени ri. Разумеется, солнечный свет не способен пробиться сквозь карамельный покров.
Сластена не отличается терпением, и ей хочется вырастить свое пирожное как можно быстрее. В ее распоряжении ровно C конфет — основной валюты Sweetland.
Любое облако можно полностью рассеять, заплатив за это ci конфет. Однако в соответствии с указом министерства метеорологии Sweetland, рассеивание более чем двух карамельных облаков искусственным путем строжайше запрещено и карается огромным штрафом.
В коллекции Сластены находится m саженцев. Она еще не определилась, какие из них достойны занять почетное место в королевском саду, и ей требуется ваша помощь. Для каждого саженца определите самую раннюю минуту, к которому его можно вырастить, не нарушая указ министерства метеорологии и не выходя за рамки бюджета. Обратите внимание, что Сластена находится на этапе формирования набора кексиков, поэтому каждый новый саженец рассматривается независимо от остальных.
Выращиваться кексики начинают в момент времени 0.
Примечание
Рассмотрим первый пример чуть подробнее. Здесь для любого k оптимально развеять облака 1 и 3. Тогда солнце не будет светить в промежутке [1..6]. Соответственно, солнечными будут являться промежутки [0..1] и [6..inf).
Во втором примере при k = 1 ничего развеивать не требуется, а при k = 5 наилучшей стратегией будет развеять облака 2 и 3. Это добавит дополнительный солнечный промежуток [4..8], который вместе с [0..1] позволяет вырастить кексик по достижении восьмой минуты.
В третьем примере два саженца кардинально различаются. Для минимизации времени выращивания первого необходимо разогнать облако 1 и получить достаточный промежуток времени [0..10], в то время как аналогичный подход даст для второго ответ 180. Однако если убрать облако 2, солнечными будут отрезки [0..3] и [7..inf), что позволит нам сократить время до 104.