Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

F. Реалистичный геймплей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно вам попался на глаза новый шутер. Говорят, данный шутер обладает реалистичными игровыми механиками.

У вашего персонажа есть пистолет с магазином в $$$k$$$ патронов и ему нужно уничтожить $$$n$$$ волн монстров. Волна $$$i$$$ состоит из $$$a_i$$$ монстров и происходит с момента времени $$$l_i$$$ по момент $$$r_i$$$. Все $$$a_i$$$ появляются в момент $$$l_i$$$ и вы должны уничтожить их всех вплоть до момента $$$r_i$$$ (вы можете убивать монстров ровно в момент $$$r_i$$$). Для каждой пары последовательных волн верно, что вторая волна начинается не раньше того момента, в который заканчивается первая волна — формально, выполняется условие $$$r_i \le l_{i + 1}$$$. Прочтите примечания к примерам из условия для более хорошего понимания процесса.

Вы уверены в своих навыках и навыках своего персонажа, а потому можете считать, что прицеливание и стрельба моментальны и что вам нужен ровно один выстрел, чтобы убить одного монстра. Однако перезарядка пистолета занимает ровно $$$1$$$ единицу времени.

Одна из реалистичных механик — это механика перезарядки: когда вы перезаряжаетесь, вы выбрасываете старый магазин вместе с оставшимися патронами. А потому постоянные перезарядки могут привести к трате огромного количества патронов.

Вам понравилась данная механика, и вам стало интересно: какое наименьшее количество патронов необходимо потратить (используя или выбрасывая), чтобы уничтожить все волны.

Заметим, что вы не выбрасываете патроны, оставшиеся после уничтожения всех волн монстров, а также начинаете игру с полным магазином.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2000$$$; $$$1 \le k \le 10^9$$$) — количество волн и размер магазина.

В следующих $$$n$$$ строках заданы описания волн. В $$$i$$$-й строке заданы три целых числа $$$l_i$$$, $$$r_i$$$ и $$$a_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$; $$$1 \le a_i \le 10^9$$$) — отрезок времени, когда происходит $$$i$$$-я волна и количество монстров в ней.

Гарантируется, что волны не пересекаются по времени (но могут касаться) и заданы в порядке появления, то есть $$$r_i \le l_{i + 1}$$$.

Выходные данные

Если не существует способа зачистить все волны, выведите $$$-1$$$. Иначе, выведите наименьшее количество патронов, которое необходимо потратить (используя или выбрасывая), чтобы уничтожить все волны врагов.

Примеры
Входные данные
2 3
2 3 6
3 4 3
Выходные данные
9
Входные данные
2 5
3 7 11
10 12 15
Выходные данные
30
Входные данные
5 42
42 42 42
42 43 42
43 44 42
44 45 42
45 45 1
Выходные данные
-1
Входные данные
1 10
100 111 1
Выходные данные
1
Примечание

В первом примере:

  • В момент $$$2$$$ начинается первая волна и появляются $$$6$$$ монстров. Вы убиваете $$$3$$$-х монстров и начинаете перезаряжаться.
  • В момент $$$3$$$ начинается вторая волна и появляются еще $$$3$$$ монстра. Вы убиваете оставшихся $$$3$$$-х монстров первой волны и начинаете перезаряжаться.
  • В момент $$$4$$$ вы убиваете оставшихся $$$3$$$-х монстров второй волны.
В результате, вы потратите $$$9$$$ патронов.

Во втором примере:

  • В момент $$$3$$$ начинается первая волна и появляются $$$11$$$ монстров. Вы убиваете $$$5$$$ монстров и начинаете перезаряжаться.
  • В момент $$$4$$$ вы убиваете еще $$$5$$$ монстров и начинаете перезаряжаться.
  • В момент $$$5$$$ вы убиваете оставшегося монстра и начинаете перезаряжаться, выбросив старый магазин с $$$4$$$ патронами.
  • В момент $$$10$$$ начинается вторая волна и появляются $$$15$$$ монстров. Вы убиваете $$$5$$$ монстров и начинаете перезаряжаться.
  • В момент $$$11$$$ вы убиваете еще $$$5$$$ монстров и начинаете перезаряжаться.
  • В момент $$$12$$$ вы убиваете последние $$$5$$$ монстров.
В результате, вы потратите $$$30$$$ патронов.