River Jump

In this problem, a person tries to cross a river by jumping between logs and river banks. The river is modeled as a two‐dimensional Cartesian plane. The left bank is the y–axis (i.e. (x=0)) and the right bank is the vertical line (x=10^9+5).

There are (n) logs floating in the river. The (i)th log is represented by its x–coordinate (x_i) and covers the vertical interval ((y_{i,1}, y_{i,2})) (note that the endpoints are not included).

The person is allowed to jump among logs and banks repeatedly. A jump from log (i) to log (j) (with (x_i \neq x_j)) is possible if and only if there exists a real number (y) such that [ y_{i,1} < y < y_{i,2} \quad \text{and} \quad y_{j,1} < y < y_{j,2}, ] and furthermore, no log (k) exists with (\min(x_i, x_j) < x_k < \max(x_i, x_j)) satisfying [ y_{k,1} < y < y_{k,2}. ] Similarly, a jump from a log to any bank is allowed (consider the bank as covering (( -\infty, \infty )) in the y–axis). Note that the left bank can jump to logs for free, while a jump originating from the (i)th log incurs a cost of (c_i). Also, the person is not allowed to jump directly from the left bank to the right bank.

The task is to determine the minimum total cost required to reach the right bank. If it is impossible to reach the right bank, output -1.

inputFormat

The first line contains an integer (n) representing the number of logs. Each of the next (n) lines contains four space–separated integers: (x_i), (y_{i,1}), (y_{i,2}) and (c_i), which denote the x–coordinate, the lower and upper bounds of the vertical interval (the jump can only occur if (y_{i,1} < y < y_{i,2})), and the cost for leaving that log, respectively.

outputFormat

Output a single integer, the minimum cost needed to cross the river from the left bank ((x=0)) to the right bank ((x=10^9+5)). If it is impossible to cross, output -1.

sample

1
5 0 10 3

3