QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 5036. 卑鄙的下毒人

Statistics

题目背景

problem_5036_1.png

题目描述

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

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

  1. 在某一原料中加入一瓶毒药,花费 $k$ 的代价,$k$ 是一个给定正整数。
  2. 在某一黄油蛋糕中加入一瓶毒药,花费 $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$