#1689. 卑鄙的下毒人

    ID: 1689 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1038来源:qoj.ac数据:公开样例二分答案

卑鄙的下毒人

卑鄙的下毒人

题目描述

标题: 卑鄙的下毒人 - Problem - QOJ.ac

#5036. 卑鄙的下毒人

Statistics

The problem was used in the following contests:

题目背景

题目描述

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2 1
1 2 1
2 3 2
2