| Codeforces Round 426 (Div. 1) |
|---|
| Закончено |
Как известно, лучшее украшение клумбы в королевстве Sweetland — ванильные кексики. Процесс их выращивания весьма сложен и требует немалых ресурсов. У Сластены есть m саженцев, и для превращения j-го саженца кексика в произведение искусства необходимо держать его под солнцем не менее kj минут.
Большую часть времени в Sweetland стоит прекрасная погода, которая лишь иногда омрачается появлением карамельных облаков, i-е из которых возникает в момент времени (минуту) li и исчезает в момент времени ri. Разумеется, солнечный свет не способен пробиться сквозь карамельный покров.
Сластена не отличается терпением, и ей хочется вырастить свое пирожное как можно быстрее. В ее распоряжении ровно C конфет — основной валюты Sweetland.
Любое облако можно полностью рассеять, заплатив за это ci конфет. Однако в соответствии с указом министерства метеорологии Sweetland, рассеивание более чем двух карамельных облаков искусственным путем строжайше запрещено и карается огромным штрафом.
В коллекции Сластены находится m саженцев. Она еще не определилась, какие из них достойны занять почетное место в королевском саду, и ей требуется ваша помощь. Для каждого саженца определите самую раннюю минуту, к которому его можно вырастить, не нарушая указ министерства метеорологии и не выходя за рамки бюджета. Обратите внимание, что Сластена находится на этапе формирования набора кексиков, поэтому каждый новый саженец рассматривается независимо от остальных.
Выращиваться кексики начинают в момент времени 0.
В первой строке следуют два числа n и C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) — число карамельных облаков и количество конфет, которыми обладает Сластена.
В следующих n строках тремя числами li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109) задается очередное карамельное облако.
Далее следует m (1 ≤ m ≤ 3·105) — число саженцев. Каждый саженец описывается одним параметром kj (1 ≤ kj ≤ 109) — необходимым числом солнечных минут.
Для каждого саженца выведите одно число — минимально возможную минуту, к которой Сластена сумеет вырастить данный ванильный кексик.
3 5
1 7 1
1 6 2
1 7 1
3
7
2
5
12
7
10
3 15
1 4 17
2 8 6
4 8 9
2
5
1
8
1
2 10
3 7 9
10 90 10
2
10
100
10
104
Рассмотрим первый пример чуть подробнее. Здесь для любого 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.
