题目描述

有一个人前来过河。

河可以抽象为一个二维坐标系上的图形。人所在的河的左岸即为 $y$ 轴，河的右岸为 $x=10^9+5$ 的直线。

河上有 $n$ 个横着的木头，第 $i$ 个木头的横坐标为 $x_i$，覆盖的点纵坐标范围为 $y_{i,1}$ 到 $y_{i,2}$。

人可以在木头与岸之间反复横跳，第 $i$ 根木头能跳到第 $j$ 根木头上，当且仅当 $x_i \not= x_j$ 且存在一个实数 $y$ 满足 $y_{i,1}<y<y_{i,2},y_{j,1}<y<y_{j,2}$ 且不存在一个木头 $k$ 满足 $\min(x_i,x_j)<x_k<\max(x_i,x_j)$ 且 $y_{k,1}<y<y_{k,2}$。同理如果一根木头想跳到岸上，把岸覆盖的 $y$ 坐标看成 $(-inf,inf)$ 也要满足这个条件。

从第 $i$ 根木头跳到别处的花费是 $c_i$，从岸上跳到别处不需要花费。左岸不能直接跳到右岸。

这个人想知道他跳到右岸最小的花费是多少。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，每行四个整数 $x_i,y_{i,1},y_{i,2},c_i$。

输出格式

一个数表示答案。保证存在一种方法使得他跳到右岸。

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $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$。

数据保证木头之间没有重叠，即不存在 $i,j$ 满足 $x_i=x_j$ 且 $y_{i,2}>y_{j,1}$。

说明

翻译自 AGM 2022 Qualification Round I River。