Сережа очень любит старые игры. Недавно он нашел у себя на компьютере одну старую приключенческую игру. Управляя героем, надо перемещаться по карте и собирать различные предметы.
На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично, с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.
Каждый лифт имеет ширину, равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).
Края пропасти находятся на одном уровне. Для каждого лифта задан диапазон высот, между которыми он перемещается, начальное положение и направление движения в начальный момент. Все лифты перемещаются со скоростью один метр в секундy. Выясните, сможет ли герой перебраться на противоположный край пропасти, и если да, то какое минимальное время ему для этого понадобится.
В первой строке вводится целое число n – количество лифтов (1 ≤ n ≤ 100). Следующие n строк содержат описания лифтов.
Каждое описание состоит из четырех целых чисел: l, u, s – самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах ( - 100 ≤ l ≤ s ≤ u ≤ 100, l < u), и d – направление движения лифта в начальный момент (d = 1 означает, что лифт двигается вверх, d = -1 – вниз).
Выведите минимальное время в секундах, необходимое для того, чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите число - 1.
## Входные Данные
В первой строке вводится целое число 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 -10 3 0 1-4 0 0 -1-2 1 0 -1Выходные данные29
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of elevators.
For each elevator $ i \in \{1, \dots, n\} $:
- $ l_i, u_i \in \mathbb{Z} $: lower and upper bounds of vertical movement.
- $ s_i \in [l_i, u_i] $: initial vertical position.
- $ d_i \in \{-1, 1\} $: initial direction (1 = up, -1 = down).
The hero starts at height 0, 2 meters from the left edge, and must end at height 0, 2 meters from the right edge.
Each elevator has width 4 meters; the hero must be at the center of an elevator to step on/off.
The hero moves horizontally at 2 m/s; vertical alignment must be exact for transitions.
Each elevator moves vertically at 1 m/s.
**Constraints**
1. $ 1 \le n \le 100 $
2. $ -100 \le l_i \le s_i \le u_i \le 100 $, $ l_i < u_i $
3. $ d_i \in \{-1, 1\} $
**Objective**
Compute the minimal time $ T \in \mathbb{R}_{\ge 0} \cup \{\infty\} $ such that the hero can traverse from the left edge (position 0) to the right edge (position $ 4n + 4 $) via elevators, stepping only when hero and elevator are vertically aligned.
The hero’s horizontal position at time $ t $ is $ x(t) = 2 + 2t $, and must satisfy:
- To step onto elevator $ i $: $ x(t) = 4(i - 0.5) $ and $ h_i(t) = 0 $
- To step off elevator $ i $ to $ i+1 $: $ x(t) = 4(i + 0.5) $ and $ h_i(t) = h_{i+1}(t) = 0 $
- To step off last elevator: $ x(t) = 4n + 2 $ and $ h_n(t) = 0 $
Elevator $ i $’s height at time $ t $:
$$
h_i(t) =
\begin{cases}
s_i + d_i t & \text{if } h_i(t) \in [l_i, u_i] \\
l_i + (u_i - l_i - (s_i + d_i t - l_i) \mod (2(u_i - l_i))) & \text{else (reflective motion)}
\end{cases}
$$
(Actual motion is periodic between $ l_i $ and $ u_i $ with reflection at bounds.)
Find minimal $ T $ such that the hero reaches $ x = 4n + 2 $ at time $ T $ with $ h_n(T) = 0 $, via a sequence of valid transitions.
If impossible, output $ -1 $.