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

Дорога начинается в посёлке Ясиня (пункт A) и заканчивается в Драгобрате (пункт B). В момент времени 0 из пункта A в пункт B и из пункта B в пункт A выходит по одной машине. Как только машина, стартовавшая из некоторого начального пункта, прибывает в свой конечный пункт, она исчезает, а из её начального пункта начинает движение следующая машина. Таким образом, на дороге в любой момент времени находятся не более двух машин.

Дорога имеет длину L и представляет собой последовательность из K однополосных и двухполосных участков некоторой длины H_i (). Известно, что 1-й и K-й участки всегда двухполосные и никакие два соседних участка не имеют равного числа полос. Пункты A и B расположены за пределами дороги. Взаиморасположение однополосных и двухполосных участков дороги продемонстрировано на рисунке:

Машина представляет собой квадрат 1 × 1, который движется по дороге в соответствии со следующими ограничениями:

— стороны машины всегда параллельны осям координат;

— машина, стартовавшая из пункта A, всегда прижимается к нижней на рисунке стороне дороги;

— машина, стартовавшая из пункта B, всегда прижимается к верхней на рисунке стороне дороги;

— модуль X-составляющей скорости движения всех машин в любой момент времени либо равен нулю, либо равен 1, при этом изменение скорости происходит мгновенно;

— временем движения по оси Y можно пренебречь (например, при перестраивании с двухполосного на однополосный участок и обратно).

Авария на дороге происходит в том случае, если квадраты, представляющие машины, имеют положительную общую площадь.

На рисунке выше случай 1 не приводит к аварии. В случае 2 авария возникнет, если машина, движущаяся влево, попытается заехать на односторонний участок до того, как другая машина полностью проедет мимо. Случай 3 приведёт к аварии, если ни одна из машин не поменяет направление движения.

Постоянные снегопады затрудняют видимость на дороге, поэтому два водителя видят друг друга только в том случае, если расстояние между машинами по оси X не превышает R. При этом машина в любом случае невидима, когда она находится за пределами дороги (перед началом движения из пункта A или B).

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

1. Если аварии не случится при условии, что скорость машин останется неизменной, то оба водителя продолжают двигаться с неизменной скоростью.
2. Если при неизменной скорости произойдёт авария, то один из водителей должен скорректировать своё движение, а другой — продолжать движение с неизменной скоростью в своем направлении. При этом водитель, корректирующий движение, выбирается так, чтобы время разъезда машин было минимальным. В случае если выбор водителя не влияет на время разъезда, то движение корректирует водитель машины, стартовавшей из пункта B.

Под временем разъезда понимается интервал между моментом времени, когда водители впервые видят друг друга, и моментом времени, когда машина, стартовавшая из пункта A, окажется полностью справа от машины, стартовавшей из пункта B. Никакие другие машины, кроме двух находящихся в текущий момент времени на дороге, при расчёте времени разъезда не учитываются.

Вам необходимо посчитать число машин, прибывших из пункта A в B и из пункта B в A за время T. Машина считается прибывшей в конечный пункт, если она полностью покинула дорогу.