题目背景
题目描述
演讲家喜欢吃黄油蛋糕，他准备用 $n$ 种原料制作 $m$ 个黄油蛋糕，第 $i$ 个黄油蛋糕由 $[l_i,r_i]$ 中的原料制成。
小鱼人想要毒死演讲家，他可以执行以下两种操作：
- 在某一原料中加入一瓶毒药，花费 $k$ 的代价，$k$ 是一个给定正整数。
- 在某一黄油蛋糕中加入一瓶毒药，花费 $1$ 的代价。
注意同一原料或同一黄油蛋糕中可以被下多次毒。
如果第 $i$ 个黄油蛋糕中，所有组成他的原料中的毒药数的和 $+$ 这个黄油蛋糕中的毒药数 $\ge a_i$，那这个黄油蛋糕就有剧毒，其中 $a_i$ 是给定正整数。
小鱼人想让所有黄油蛋糕都有剧毒，最少代价？
输入格式
第一行三个正整数 $n,m,k$，分别表示原料数量，黄油蛋糕数量，在原料中下毒的代价。
之后 $m$ 行，每行两个整数 $l_i,r_i,a_i$，意义见题目描述。
输出格式
一行一个整数，表示最少代价。
输入样例
3 2 1
1 2 1
2 3 2输出样例
2数据范围
对于所有数据，$1\le n,m \le 5\times 10^5,1\le k\le 5,1\le a_i\le 10^9$
| 子任务编号 | $n \le $ | $m \le $ | $k \le $ | $a_i \le $ | 分值 |
|---|---|---|---|---|---|
| $1$ | $20$ | $20$ | $5$ | $1$ | $10$ |
| $2$ | $5\,000$ | $5\,000$ | $10^9$ | $20$ | |
| $3$ | $5 \times 10^5$ | $5 \times 10^5$ | $1$ | $20$ | |
| $4$ | $5$ | $1$ | $20$ | ||
| $5$ | $10^9$ | $30$ |