题目描述

萨什卡有一块很长的木板，被划分为 $N$ 个等长区间，编号为 $1$ 到 $N$。初始时，所有区间都被霉菌感染。

她有 $M$ 个可选的清理操作。对于操作 $i$，给定：

• 可执行日期 $T_i$；
• 清理范围 $[L_i,R_i]$；
• 费用 $C_i$。

若选择该操作，则在第 $T_i$ 天晚上，区间 $[L_i,R_i]$ 中所有仍被感染的位置都会被清理干净。

霉菌会继续扩散。若某个位置在某天早晨被感染，那么在当天中午，感染会扩散到它的左右相邻位置（若存在）。因此，一个已经清理过的位置之后仍可能再次被感染。

每天的顺序为：

1. 霉菌先从所有感染位置向相邻位置扩散一步；
2. 萨什卡再执行当天所选择的全部清理操作。

同一天可以执行任意多个操作。

请从 $M$ 个操作中选择一个子集，使所有操作执行完毕后，整块木板上不再有任何感染位置，并最小化总费用。

若无法完全清理，返回 $-1$。

实现要求

提交 mold.cpp，包含 mold.h，并实现：

long long min_cost(
    int N,
    std::vector<int> T,
    std::vector<int> L,
    std::vector<int> R,
    std::vector<int> C
);

其中四个向量长度均为 $M$，描述所有清理操作。函数只调用一次。

数据范围

• $1\le N\le 10^9$；
• $1\le M\le 100\,000$；
• $1\le T_i\le 10^9$；
• $1\le L_i\le R_i\le N$；
• $1\le C_i\le 10^9$。

子任务

本地评测器格式

输入

N M
T1 L1 R1 C1
T2 L2 R2 C2
...
TM LM RM CM

输出

输出 min_cost 的返回值。

样例

样例 1

输入：
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

输出：
7

选择操作 $1,3,5$，总费用为 $3+3+1=7$。

样例 2

输入：
10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1

输出：
-1

样例 3

输入：
10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1

输出：
7