CF313D Ilya and Roads

Ilya 所在的城市一切都很好，除了道路。事实上，唯一的一条 ZooVille 道路可以表示为一行共 $n$ 个坑。我们认为这些坑从左到右编号为 $1$ 到 $n$。 Ilya 非常热心于帮助他的城市。所以，他希望在唯一的 ZooVille 道路上修复至少 $k$ 个坑（也许可以修复更多）。 城市里有 $m$ 家建筑公司，第 $i$ 家公司需要 $c_i$ 单位的钱来修复一段包含从 $l_i$ 到 $r_i$（包括两端）编号坑的道路段。ZooVille 的公司非常贪婪，所以如果他们修复的路段中包含了一些已经被修复过的坑，他们的报价并不会因此减少。 请你计算，Ilya 修复至少 $k$ 个坑所需的最小金钱数。

第一行包含三个整数 $n, m, k$（$1 \le n \le 300, 1 \le m \le 10^5, 1 \le k \le n$）。接下来的 $m$ 行每行包含三个整数 $l_i, r_i, c_i$（$1 \le l_i \le r_i \le n, 1 \le c_i \le 10^9$），描述第 $i$ 家公司的信息。

输出一个整数——Ilya 修复至少 $k$ 个坑所需的最小金钱数。如果无法修复至少 $k$ 个坑，则输出 $-1$。

由 ChatGPT 5 翻译