1430: Holiday scheduling: episode 2
题目
题目描述
请注意：相比 episode 1，本题 $1 \leq x \leq 10 ^ 9, 1 \leq a_i \leq 10 ^ 9$。
你有 $n$ 天的假期，每一天你有三种选择：
- 发呆。你不需要花钱，但也没有任何收入。
- 花费 $x$ 元出去玩一天。
- 打工。有 $m$ 项任务可以选择，第 $i$ 项需要占用你第 $s_i$ 到 $t_i$ 天的时间，完成一个任务可以获得 $a_i$ 元。你不能在某一天同时打两份工。
你最开始有 $0$ 元。由于打工和发呆很无聊，你想在玩的天数尽可能多的情况下，赚尽量多的钱。
请输出你在假期结束后，最终会剩下多少钱。
Input
请从 stdin 读入。
输入第一行为三个正整数，$n, m, x~ (1 \leq n \leq 365, 1\leq m \leq 10^5, 1 \leq x \leq 10 ^ 9)$.
接下来 $m$ 行，第 $i$ 行有三个正整数 $s_i, t_i, a_i (1 \leq s_i \leq t_i \leq n, 1 \leq a_i \leq 10 ^ 9)$。
Output
请输出到 stdout 中。
输出一行一个整数，表示你在假期结束后，最终会剩下多少钱。
Sample Input
3 3 1
1 1 2
1 2 1000000000
2 3 1000000000
3 3 1
1 3 1000000000
2 3 1000000000
3 3 1000000000
Sample Output
0
1000000000
Note
样例 1 解释：人生得意须尽欢，莫使金樽空对月！
样例 2 解释：金樽空对月。
Constraints
Time Limit: 1s
Memory Limit: 128MB
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！