D. Максимальный водопад
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Эмускальда наняли на разработку искусственного водопада в соответствии с последними тенденциями в ландшафтной архитектуре. Современный искусственный водопад состоит из нескольких горизонтальных панелей, прикрепленных к широкой плоской стене. Вода течет вниз, начиная от верха стены, от панели к панели, пока не достигнет нижней части стены.

Стена имеет высоту t. К ней прикреплены n панелей. Каждая панель представляет собой горизонтальный отрезок на высоте hi, который начинается с li и заканчивается в ri. Панель номер i соединяет точки стены (li, hi) и (ri, hi). Верхняя часть стены считается панелью, соединяющей точки (  -  109,  t) и (109,  t). Аналогично, нижняя часть стены соединяет точки (  -  109,  0) и (109,  0). Никакие две панели не имеют общую точку.

Эмускальд знает, что для того, чтобы водопад выглядел эффектно, он может течь с панели i на панель j (), только если выполнены следующие условия:

  1. max(li, lj) < min(ri, rj) (горизонтальные проекции панелей перекрываются);
  2. hj < hi (панель j ниже панели i);
  3. нет такой панели k (hj < hk < hi), что первые два условия выполняются для пар панелей (i, k) и (k, j).

Тогда поток по равняется min(ri, rj) - max(li, lj), длине пересечения их горизонтальных проекций.

Эмускальд решил, что в его водопаде вода будет течь по одному пути сверху вниз. Если вода падает на какую-то панель (исключая низ стены), то далее вода должна падать ровно на одну панель ниже нее. Общий поток воды в таком водопаде определяется как минимум величин пересечения горизонтальных проекций между двумя соседними панелями на пути водопада. Более формально:

  1. водопад состоит из одного пути панелей ;
  2. поток водопада равняется минимальному потоку на пути .

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

Помогите Эмускальду поддержать свою репутацию и найдите значение максимально возможного потока воды в некотором водопаде.

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

Первая строка входных данных состоит из двух целых чисел n и t (1 ≤ n ≤ 105, 2 ≤ t ≤ 109), записанных через пробел — количество панелей, не считая верхнюю и нижнюю панели, и высота стены. Каждая из последующих n строк содержит по три целых числа через пробел hi, li и ri (0 < hi < t,  - 109 ≤ li < ri ≤ 109) — высота, левый и правый концы отрезка i-ой панели.

Гарантируется, что никакие две панели не имеют общих точек.

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

Выведите единственное целое число — максимально возможную величину потока воды в искомом водопаде.

Примеры
Входные данные
5 6
4 1 6
3 2 7
5 9 11
3 10 15
1 13 16
Выходные данные
4
Входные данные
6 5
4 2 8
3 1 2
2 2 3
2 6 12
1 0 7
1 8 11
Выходные данные
2
Примечание

Первый тест соответствует картинке.