C. Хакер, собирай чемоданы!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, лучший способ отвлечься от чего-либо — заниматься своим любимым делом. Для хакера Лехи любимое дело это работа.

Чтобы не скучать, Леха начал усердно работать, то есть взламывать компьютеры по всему миру. За такое усердие начальство дало хакеру отпуск продолжительностью ровно x дней. Как известно, большинство людей предпочитают куда-нибудь уехать на время отпуска, поэтому Леха сразу пошёл в туристическое агенство. Там он выяснил, что осталось n непроданных путевок. i-я путевка характеризуется тремя числами li, ri, costi — день отъезда из Вичкополиса, день возврата в Вичкополис и стоимость путевки соответственно. Продолжительностью i-й путевки называют величину ri - li + 1.

При этом Леха хочет разделить свой отпуск на две части. Кроме того он хочет потратить как можно меньше денег. Более формально, Леха хочет выбрать ровно две путевки i и j (i ≠ j) так, чтобы они не пересекались, сумма их продолжительностей была равна ровно x, а суммарная стоимость была минимальна. Две путевки i и j не пересекаются, если выполняется хотя бы одно из условий: ri < lj или rj < li.

Помогите Лехе выбрать необходимые путевки!

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

В первой строке заданы два целых числа n и x (2 ≤ n, x ≤ 2·105) — количество путевок в туристическом агентстве и продолжительность отпуска соответственно.

В следующих n строках следуют по три целых числа li, ri и costi (1 ≤ li ≤ ri ≤ 2·105, 1 ≤ costi ≤ 109) — описание очередной путевки.

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

Выведите одно целое число — минимальное количество денег, которые потратит Леха, либо  - 1, если невозможно выбрать две непересекающиеся путевки с суммарной продолжительностью ровно x.

Примеры
Входные данные
4 5
1 3 4
1 2 5
5 6 1
1 2 4
Выходные данные
5
Входные данные
3 2
4 6 3
2 4 1
3 5 4
Выходные данные
-1
Примечание

В первом примере примере Леха должен выбрать первую и третью путевки. Тогда их суммарная продолжительность будет равна (3 - 1 + 1) + (6 - 5 + 1) = 5, а суммарная стоимость будет равна 4 + 1 = 5.

Во втором примере продолжительность каждой из путевок равна 3, поэтому невозможно выбрать две путевки с суммарной продолжительностью равной 2.