卑鄙的下毒人 - Problem

演讲家喜欢吃黄油蛋糕，他准备用 $n$ 种原料制作 $m$ 个黄油蛋糕，第 $i$ 个黄油蛋糕由 $[l_i,r_i]$ 中的原料制成。

小鱼人想要毒死演讲家，他可以执行以下两种操作：

注意同一原料或同一黄油蛋糕中可以被下多次毒。

如果第 $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

对于所有数据， $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$	$5$	$10^9$	$20$
$3$	$5 \times 10^5$	$5 \times 10^5$	$1$	$10^9$	$20$
$4$			$5$	$1$	$20$
$5$			$5$	$10^9$	$30$

QOJ.ac