Input

6 8 2
2 5
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7

Output

19

Ràng buộc:

- Có 50% số test ứng với 50% số điểm của bài có n<=100 và k<=5.
- Có 50% số test khác ứng với 50% số điểm còn lại của bài có n<=1000 và k<=15. 

Nguồn: 3D '1819