Карам учится в очень крутой школе. В конце каждого учебного года все ученики, даже самые одарённые и талантливые, подвергаются сдаче зачёта. В одной из таких зачетных работ по информатике Караму предстояло решить одну интересную задачу.
Задача состояла в следующем: на прямой отмечено $$$m$$$ точек, пронумерованных от $$$1$$$ до $$$m$$$. Также было дано $$$n$$$ отрезков, которые были пронумерованы от $$$1$$$ до $$$n$$$. Отрезок под номером $$$i$$$ мог покрыть точки с номерами от $$$l_i$$$ до $$$r_i$$$ включительно, и за такое покрытие взималась определенная стоимость $$$c_i$$$. Задача заключалась в том, чтобы покрыть все $$$m$$$ данных точек, стараясь при этом минимизировать затраты.
Конечно же, Карам успешно справился с этой задачей и получил высокую оценку. Однако, он начал задумываться, что произойдет, если покрыть не все $$$m$$$ точек прямой, а оставить непокрытой ровно одну любую точку. Это стало для него интересным вызовом. Справитесь ли вы с этой задачей?
Первая строка входных данных содержит два числа $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 300\ 000)$$$ — количество отрезков и количество точек на прямой соответственно.
В следующих $$$n$$$ строках описываются отрезки. Каждая строка содержит три целых числа $$$l_i$$$, $$$r_i$$$, $$$c_i$$$ $$$(1 \le l_i \le r_i \le m,\ 1 \le c_i \le 10^9)$$$ — границы отрезка и его стоимость cоответственно.
Выведите стоимость минимального покрытия $$$m - 1$$$ точки прямой или $$$-1$$$, если это невозможно.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные ограничения | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 11 | $$$1 \le m \le 2$$$ | – | На прямой отмечено всего две точки. |
| 2 | 14 | $$$1 \le n, m \le 15$$$ | 0 | |
| 3 | 21 | $$$1 \le n, m \le 1000$$$ | 0, 2 | |
| 4 | 21 | $$$1 \le n, m \le 300\ 000$$$ | – | Оптимально оставить непокрытой первую точку. Гарантируется, что ответ есть. |
| 5 | 33 | $$$1 \le n, m \le 300\ 000$$$ | 0-4 |
4 3 1 1 3 1 2 8 2 2 4 3 3 2
5
3 10 1 5 13 3 10 23 5 7 11
-1
Давайте разберем первый пример.
Иллюстрация к первому примеру. Можно оставить непокрытой первую точку, используя третий и четвертый отрезок, тогда стоимость покрытия будет равна $$$c_3 + c_4 = 4 + 2 = 6$$$.
Иллюстрация к первому способу. Вторую точку можно оставить непокрытой, используя первый и четвертый отрезок, тогда стоимость покрытия будет равна $$$c_1 + c_4 = 3 + 2 = 5$$$.
Иллюстрация к второму способу. Все точки, кроме третьей, можно покрыть, используя первый и третий отрезки, либо используя только второй отрезок. Стоимости таких покрытий будут равны $$$c_1 + c_3 = 7$$$ и $$$c_2 = 8$$$ соответственно.
Иллюстрация к третьему способу. 
Иллюстрация к четвертому способу. Получается, что самым дешевым способом покрыть все точки, кроме одной, будет стоить $$$c_1 + c_4 = 5$$$.
Во втором примере несложно заменить, что невозможно покрыть прямую так, чтобы непокрытой осталась ровно одна точка.
