CF313D.Ilya and Roads

Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as n holes in a row. We will consider the holes numbered from 1 to n, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at least k holes (perharps he can fix more) on a single ZooVille road.

The city has m building companies, the i-th company needs c__i money units to fix a road segment containing holes with numbers of at least l__i and at most r__i. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.

Determine the minimum money Ilya will need to fix at least k holes.

伊利亚所在的城市一切都很好，唯独道路状况堪忧。事实上，整个动物园城（ZooVille）仅有一条道路，它被建模为一排共 $n$ 个洞。我们将这些洞从左到右依次编号为 $1$ 到 $n$。

伊利亚非常热衷于帮助自己的城市，因此他希望在这条动物园城道路上至少修复 $k$ 个洞（也可能修复更多）。

该城市共有 $m$ 家建筑公司，其中第 $i$ 家公司修复一段道路所需费用为 $c_i$ 个货币单位，该段道路必须恰好覆盖编号在 $[l_i, r_i]$ 范围内的所有洞（即包含编号 $\ge l_i$ 且 $\le r_i$ 的所有洞）。动物园城的建筑公司极其贪婪：若某家公司所修复的路段中已存在已被修复的洞，该公司不会因此降低收费。

请确定伊利亚修复至少 $k$ 个洞所需的最少资金。

The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). The next m lines contain the companies' description. The i-th line contains three integers l__i, r__i, c__i (1 ≤ l__i ≤ r__i ≤ n, 1 ≤ c__i ≤ 109).

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

Print a single integer — the minimum money Ilya needs to fix at least k holes.

If it is impossible to fix at least k holes, print -1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——Ilya 修复至少 k 个洞所需的最少金额。

如果无法修复至少 k 个洞，则输出 -1。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。