题目描述

由于农夫的奶牛们非常爱干净，它们要求牛棚必须保持一尘不染。农夫约翰不得不雇用一些奶牛来清扫牛棚。

农夫约翰有 $N$（$1 \le N \le 10{,}000$）头奶牛愿意参加清扫工作。由于灰尘会不断落下，清扫工作必须在一天中的某个连续时间段内持续进行，这个工作时间段是从第 $M$ 秒到第 $E$ 秒（$0 \le M \le E \le 86{,}399$）。注意：需要清扫的总时间为 $E-M+1$ 秒。在 $M$ 到 $E$ 的每一秒内，至少都要有一头奶牛在清扫。

每头奶牛都提交了一份工作申请，表明她愿意在某个特定的时间区间 $T_1$ 到 $T_2$（其中 $M \le T_1 \le T_2 \le E$）内工作，并索取 $S$ 的佣金（$0 \le S \le 500{,}000$）。注意，一头申请在区间 $10$ 到 $20$ 工作的奶牛将工作 $11$ 秒，而不是 $10$ 秒。农夫约翰必须全部接受或全部拒绝每份申请；他不能让一头奶牛只工作她所申请时间的一部分，并支付相应部分的佣金。

请你设计一个清扫方案，使得工作日的每一秒都至少有一头奶牛在清扫，并且支付给奶牛的总佣金最少。

输入格式

• 第一行：三个用空格分开的整数 $N$、$M$ 和 $E$。
• 第 $2$ 到第 $N+1$ 行：第 $i+1$ 行描述了第 $i$ 头奶牛的工作安排，包含三个用空格分开的整数：$T_1$、$T_2$ 和 $S$。

输出格式

• 一行：一个整数，表示完成牛棚清扫所需的最少总佣金；如果无法完成清扫，则输出 $-1$。

数据范围

• $1 \le N \le 10{,}000$
• $0 \le M \le E \le 86{,}399$
• 对于每头奶牛：$M \le T_1 \le T_2 \le E$
• $0 \le S \le 500{,}000$

输入样例

3 0 4
0 2 3
3 4 2
0 0 1

输出样例

5

样例解释

农夫约翰有三头奶牛，牛棚需要从第 0 秒清扫到第 4 秒。

• 第一头奶牛愿意在第 0、1、2 秒工作，总佣金为 3。
• 第二头奶牛愿意在第 3、4 秒工作，总佣金为 2。
• 第三头奶牛只愿意在第 0 秒工作，佣金为 1。

农夫约翰可以雇用前两头奶牛。这样：

• 第 0、1、2 秒由第一头奶牛清扫。
• 第 3、4 秒由第二头奶牛清扫。
• 每个时刻都有奶牛在工作，且总佣金为 $3+2=5$，这是最小的可能值。