Problem Description

A person comes to cross a river.

The river can be viewed as a shape on a 2D coordinate system. The left bank where the person starts is the $y$-axis, and the right bank is the line $x=10^9+5$.

There are $n$ horizontal logs on the river. The $i$-th log has $x$-coordinate $x_i$, and it covers points whose $y$-coordinate ranges from $y_{i,1}$ to $y_{i,2}$.

The person can jump back and forth between logs and the banks. The $i$-th log can jump to the $j$-th log if and only if $x_i \not= x_j$ and there exists a real number $y$ such that $y_{i,1}<y<y_{i,2},y_{j,1}<y<y_{j,2}$, and there does not exist a log $k$ such that $\min(x_i,x_j)<x_k<\max(x_i,x_j)$ and $y_{k,1}<y<y_{k,2}$. Similarly, if a log wants to jump to a bank, treat the $y$-range covered by the bank as $(-inf,inf)$, and the same condition must be satisfied.

The cost to jump from the $i$-th log to anywhere else is $c_i$. Jumping from a bank to anywhere else costs nothing. The left bank cannot jump directly to the right bank.

The person wants to know the minimum total cost to reach the right bank.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain four integers $x_i,y_{i,1},y_{i,2},c_i$.

Output Format

Output one number representing the answer. It is guaranteed that there exists a way to reach the right bank.

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

Hint

Constraints

For $100\%$ of the testdata, $1\leq n\leq 2.5\times 10^5$, $1\leq x_i,c_i\leq 10^9$, $1\leq y_{i,1}\leq y_{i,2}\leq 10^9$.

The testdata guarantees that logs do not overlap: there do not exist $i,j$ such that $x_i=x_j$ and $y_{i,2}>y_{j,1}$.

Notes

Translated from AGM 2022 Qualification Round I River。

Translated by ChatGPT 5