Sửa đường

Ở thành phố của An mọi thứ đều tốt đẹp, ngoại trừ một con đường. Con đường này có $n$ cái hố xếp theo một hàng. Chúng ta đánh số các hố này từ 1 đến $n$ theo thứ tự từ đầu đến cuối con đường.

An thực sự muốn giúp thành phố của mình. Vì vậy, anh ta muốn sửa chữa ít nhất $k$ cái hố (có thể anh ta sửa chữa nhiều hơn) trên con đường này.

Thành phố có $m$ công ty sửa đường, công ty thứ $i$ cần $c_i$ đơn vị tiền để sửa chữa một đoạn đường có chứa các hố với chỉ số nhỏ nhất là $l_i$ và lớn nhất là $r_i$. Các công ty này rất tham lam, vì vậy nếu họ sửa chữa một đoạn đường có chứa một số hố đã được sửa, họ không giảm giá sửa chữa đoạn đường này.

Hãy xác định số tiền tối thiểu mà An sẽ cần để sửa chữa ít nhất $k$ cái hố.

Vào từ tệp roa.inp. Dòng đầu tiên chứa 3 số nguyên $n, m, k$ ($1 \le n \le 300; 1 \le m \le 10^5; 1 \le k \le n$). Dòng thứ $i$ trong $m$ dòng tiếp theo chứa 3 số nguyên $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le n; 1 \le c_i \le 10^9$) mô tả công ty thứ $i$ cần $c_i$ đơn vị tiền để sửa chữa đoạn đường từ hố $l_i$ đến $r_i$.

Ghi ra tệp roa.out một số nguyên là số tiền tối thiểu mà An cần để sửa chữa ít nhất $k$ cái hố. Trong trường hợp không thể sửa ít nhất $k$ cái hố thì ghi ra số $-1$.

• Có 10% số test ứng với 10% số điểm thỏa mãn: $k = 1$;
• 15% số test khác ứng với 15% số điểm thỏa mãn: $1 \le l_i = r_i \le n$ với mọi $i = 1, 2, \ldots, m$;
• 20% số test khác ứng với 20% số điểm thỏa mãn: $1 \le m \le 20$;
• 25% số test khác ứng với 25% số điểm thỏa mãn: $1 \le n \le 100$ và $1 \le m \le 1000$;
• 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.