← 返回题目列表

Codeforces · 313/D

D. 伊利亚和道路

中文机器翻译题面 查看原题

伊利亚的城市一切都很棒,除了道路。问题是,ZooVille 唯一的道路被表示为连续的 n 个洞。我们将从左到右考虑编号为 1 到 n 的孔。

伊利亚确实在继续帮助他的城市。因此,他想在 ZooVille 的一条道路上修复至少 k 个洞(也许他可以修复更多)。

该市有 m 个建筑公司,第 i 个公司需要 ci 单位资金来修复含有至少 li 和最多 ri 数量孔洞的路段。 ZooVille 中的公司非常贪婪,因此,如果他们修复包含一些已修复漏洞的段,他们不会降低修复该段的价格。

确定 Ilya 修复至少 k 个洞所需的最低金额。

输入

第一行包含三个整数 n、m、k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n)。接下来的 m 行包含公司的描述。第 i 行包含三个整数 li、ri、ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109)。

输出

打印一个整数——Ilya 修复至少 k 个洞所需的最低金额。

如果无法修复至少 k 个孔,则打印 -1。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

10 4 6
7 9 11
6 9 13
7 7 7
3 5 6

输出 #1

17

输入 #2

10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13

输出 #2

2

输入 #3

10 1 9
5 10 14

输出 #3

-1