Задача . D. Максимальный водопад

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

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

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

1. max(l_i, l_j) < min(r_i, r_j) (горизонтальные проекции панелей перекрываются);
2. h_j < h_i (панель j ниже панели i);
3. нет такой панели k (h_j < h_k < h_i), что первые два условия выполняются для пар панелей (i, k) и (k, j).

Тогда поток по равняется min(r_i, r_j) - max(l_i, l_j), длине пересечения их горизонтальных проекций.

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

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

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

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