Skip to content

1430: Holiday scheduling: episode 2

题目

题目描述

请注意:相比 episode 1,本题 $1 \leq x \leq 10 ^ 9, 1 \leq a_i \leq 10 ^ 9$。

你有 $n$ 天的假期,每一天你有三种选择:

  1. 发呆。你不需要花钱,但也没有任何收入。
  2. 花费 $x$ 元出去玩一天。
  3. 打工。有 $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了,可以的话,请您参考添加页面,与大家一起分享你的题解!