Рабочее место участника

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

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

Каждый лифт имеет ширину равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).

Края пропасти находятся на одном уровне. Для каждого лифта задан диапазон высот, между которыми он перемещается, начальное положение и направление движения в начальный момент. Все лифты перемещаются со скоростью один метр в секундy. Выясните, сможет ли герой перебраться на противоположный край пропасти, и если да, то какое минимальное время ему для этого понадобится.

Первая строка входного файла содержит целое число `n` — количество лифтов (`1\ ≤\ n\ ≤\ 100`). Следующие `n` строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: `l`, `u`, `s` — самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах (`-100\ ≤\ l\ ≤\ s\ ≤\ u\ ≤\ 100`, `l\ <\ u`), и `d` — направление движения лифта в начальный момент (`d\ =\ 1` означает, что лифт двигается вверх, `d\ =\ -1` — вниз).

Выведите в выходной файл минимальное время в секундах, необходимое чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите в выходной файл `-1`.

4
-1 2 1 -1
0 3 0 1
-4 0 0 -1
-2 1 0 -1

29