409514: GYM103604 I River

River wants to cross a Bob. Oh no... I mean Bob wants to cross the AGM River (Amazing Great Massive River).

The AGM River is very wide so Bob cannot jump directly from the left side of the river to the right side. Fortunately for him, there are a lot of wooden logs floating on the river that he can jump on. These can be described as tuples $$$(x, y1, y2, c)$$$, signifying there is a log between $$$(x, y1)$$$ and $$$(x, y2)$$$ that takes $$$c$$$ energy for Bob to jump from (the logs shape vary and it's harder to keep your balance on some and easier on others).

Since the logs are so slippery, Bob can only jump horizontally and only between adjacent logs (i.e. he cannot jump over logs). Bob can freely move on a log. Formally, two logs $$$l_i = (x_i, y_{i_1}, y_{i_2}, c_i)$$$ and $$$l_j = (x_j, y_{j_1}, y_{j_2}, c_j)$$$ (where $$$x_i < x_j$$$) are adjacent if: $$$\exists\ d = y$$$ a horizontal line such as $$$y_{i_1} < y < y_{i_2}$$$ and $$$y_{j_1} < y < y_{j_2}$$$, and $$$\nexists\ l_k = (x_k, y_{k_1}, y_{k_2}, c_k)$$$ such as $$$x_i < x_k < x_j$$$ and $$$y_{k_1} < y < y_{k_2}$$$. If two such logs $$$l_i$$$ and $$$l_j$$$ exist, Bob will spend $$$c_i$$$ energy jumping from $$$l_i$$$ to $$$l_j$$$, and $$$c_j$$$ energy jumping from $$$l_j$$$ to $$$l_i$$$.

The first jump will start from the left side of the river (to the left of the leftmost log) to an adjacent log. This jump takes $$$0$$$ energy. The last jump will end on the right side of the river (to the right of the rightmost log) and will start from an adjacent log $$$l_r = (x_r, y_{r_1}, y_{r_2}, c_r)$$$. This takes $$$c_r$$$ energy.

Bob wants to conserve his energy for inventing new algorithms, so he asks you to find out what's the least energy he can spend in order to cross the river.

On the first line of the input you're given an integer $$$N$$$ ($$$1 \leq N \leq 250000$$$), the number of logs floating on the AGM River.

The following $$$N$$$ lines will each contain a tuple $$$(x_i, y_{i_1}, y_{i_2}, c_i)$$$, the description of the $$$i^{th}$$$ log ($$$1 \leq x_i \leq 10^9$$$, $$$1 \leq y_{i_1} \leq 10^9$$$, $$$1 \leq y_{i_2} \leq 10^9$$$, $$$y_{i_1} < y_{i_2}$$$, $$$1 \leq c_i \leq 10^9$$$).

There are no overlapping logs. That is, $$$\forall$$$ $$$l_i=(x_i, y_{i_1}, y_{i_2}, c_i)$$$ and $$$l_j=(x_j, y_{j_1}, y_{j_2}, c_i)$$$, if $$$x_i = x_j$$$ then $$$y_{i_2} \leq y_{j_1}$$$ or $$$y_{j_2} \leq y_{i1}$$$.

For each log $$$i$$$, the interval $$$(y_{i_1}, y_{i_2})$$$ is open, i.e. the ends $$$y_{i_1}$$$ and $$$y_{i_2}$$$ are not considered part of the interval.

The output file should contain a single integer, the answer to Bob's query.

8
1 1 4 10
4 2 5 10
2 3 5 1
3 2 4 1
2 1 3 1
5 1 3 1
6 1 2 10
6 2 3 10

4

Explanation for the above example: