#PQJ1038x5036. QOJ 1038_5036
QOJ 1038_5036
标题: 卑鄙的下毒人 - Problem - QOJ.ac
#5036. 卑鄙的下毒人
The problem was used in the following contests:
题目背景
题目描述
演讲家喜欢吃黄油蛋糕,他准备用 n 种原料制作 m 个黄油蛋糕,第 i 个黄油蛋糕由 [li,ri] 中的原料制成。
小鱼人想要毒死演讲家,他可以执行以下两种操作:
- 在某一原料中加入一瓶毒药,花费 k 的代价,k 是一个给定正整数。
- 在某一黄油蛋糕中加入一瓶毒药,花费 1 的代价。
注意同一原料或同一黄油蛋糕中可以被下多次毒。
如果第 i 个黄油蛋糕中,所有组成他的原料中的毒药数的和 + 这个黄油蛋糕中的毒药数 ≥ai,那这个黄油蛋糕就有剧毒,其中 ai 是给定正整数。
小鱼人想让所有黄油蛋糕都有剧毒,最少代价?
输入格式
第一行三个正整数 n,m,k,分别表示原料数量,黄油蛋糕数量,在原料中下毒的代价。
之后 m 行,每行两个整数 li,ri,ai,意义见题目描述。
输出格式
一行一个整数,表示最少代价。
输入样例
3 2 1
1 2 1
2 3 2
输出样例
2
数据范围
对于所有数据,1≤n,m≤5×105,1≤k≤5,1≤ai≤109
子任务编号 n≤ m≤ k≤ ai≤ 分值 1 20 20 5 1 10 2 5000 5000 109 20 3 5×105 5×105 1 20 4 5 1 20 5 109 30