| Codeforces Round 165 (Div. 1) |
|---|
| Закончено |
Эмускальда наняли на разработку искусственного водопада в соответствии с последними тенденциями в ландшафтной архитектуре. Современный искусственный водопад состоит из нескольких горизонтальных панелей, прикрепленных к широкой плоской стене. Вода течет вниз, начиная от верха стены, от панели к панели, пока не достигнет нижней части стены.
Стена имеет высоту t. К ней прикреплены n панелей. Каждая панель представляет собой горизонтальный отрезок на высоте hi, который начинается с li и заканчивается в ri. Панель номер i соединяет точки стены (li, hi) и (ri, hi). Верхняя часть стены считается панелью, соединяющей точки ( - 109, t) и (109, t). Аналогично, нижняя часть стены соединяет точки ( - 109, 0) и (109, 0). Никакие две панели не имеют общую точку.
Эмускальд знает, что для того, чтобы водопад выглядел эффектно, он может течь с панели i на панель j (
), только если выполнены следующие условия:
- max(li, lj) < min(ri, rj) (горизонтальные проекции панелей перекрываются);
- hj < hi (панель j ниже панели i);
- нет такой панели k (hj < hk < hi), что первые два условия выполняются для пар панелей (i, k) и (k, j).
Тогда поток по равняется min(ri, rj) - max(li, lj), длине пересечения их горизонтальных проекций.
Эмускальд решил, что в его водопаде вода будет течь по одному пути сверху вниз. Если вода падает на какую-то панель (исключая низ стены), то далее вода должна падать ровно на одну панель ниже нее. Общий поток воды в таком водопаде определяется как минимум величин пересечения горизонтальных проекций между двумя соседними панелями на пути водопада. Более формально:
- водопад состоит из одного пути панелей
; - поток водопада равняется минимальному потоку на пути .
Для того, чтобы сделать действительно грандиозный водопад, Эмускальд должен максимизировать этот поток воды, но на стене слишком много панелей, и он с трудом планирует свое детище. Ниже приведен пример одного из водопадов, который хочет установить Эмускальд:
Помогите Эмускальду поддержать свою репутацию и найдите значение максимально возможного потока воды в некотором водопаде.
Первая строка входных данных состоит из двух целых чисел 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
Первый тест соответствует картинке.
