Как известно, лучший способ отвлечься от чего-либо — заниматься своим любимым делом. Для хакера Лехи любимое дело это работа.
Чтобы не скучать, Леха начал усердно работать, то есть взламывать компьютеры по всему миру. За такое усердие начальство дало хакеру отпуск продолжительностью ровно x дней. Как известно, большинство людей предпочитают куда-нибудь уехать на время отпуска, поэтому Леха сразу пошёл в туристическое агенство. Там он выяснил, что осталось n непроданных путевок. i-я путевка характеризуется тремя числами li, ri, costi — день отъезда из Вичкополиса, день возврата в Вичкополис и стоимость путевки соответственно. Продолжительностью i-й путевки называют величину ri - li + 1.
При этом Леха хочет разделить свой отпуск на две части. Кроме того он хочет потратить как можно меньше денег. Более формально, Леха хочет выбрать ровно две путевки i и j (i ≠ j) так, чтобы они не пересекались, сумма их продолжительностей была равна ровно x, а суммарная стоимость была минимальна. Две путевки i и j не пересекаются, если выполняется хотя бы одно из условий: ri < lj или rj < li.
Помогите Лехе выбрать необходимые путевки!
Выходные данные
Выведите одно целое число — минимальное количество денег, которые потратит Леха, либо - 1, если невозможно выбрать две непересекающиеся путевки с суммарной продолжительностью ровно x.
Примечание
В первом примере примере Леха должен выбрать первую и третью путевки. Тогда их суммарная продолжительность будет равна (3 - 1 + 1) + (6 - 5 + 1) = 5, а суммарная стоимость будет равна 4 + 1 = 5.
Во втором примере продолжительность каждой из путевок равна 3, поэтому невозможно выбрать две путевки с суммарной продолжительностью равной 2.