伊利亚的城市一切都很棒,除了道路。问题是,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