首页 > 试题广场 >

CodeForces 313D Ilya and Roads

[编程题]CodeForces 313D Ilya and Roads

时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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.

输入描述:

The first line contains three integers n, m, k(1 ≤ n ≤ 300, 1 ≤ m ≤ 10⁵, 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 ≤ 10⁹).

输出描述:

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.

示例1

输入

10 4 6<br />7 9 11<br />6 9 13<br />7 7 7<br />3 5 6<br />10 7 1<br />3 4 15<br />8 9 8<br />5 6 8<br />9 10 6<br />1 4 2<br />1 4 10<br />8 10 13<br />10 1 9<br />5 10 14<br />