Môi giới bất động sản

Trong một buổi khảo sát thị trường bất động sản, FullHouse Dev được giao nhiệm vụ phân tích chi phí môi giới tại một con phố. Họ nhận thấy rằng việc tính toán chi phí môi giới tối thiểu là một bài toán thú vị cần được giải quyết.

Bài toán

Có \(n\) môi giới bất động sản trong thành phố. Trên một con phố có \(m\) căn nhà xếp thành một hàng thẳng và được đánh số từ \(1\) đến \(m\). Môi giới thứ \(i\) phụ trách bán các căn nhà có số từ \(l_i\) đến \(r_i\) và nhận được \(c_i\) đô la tiền hoa hồng.

Lưu ý: Mỗi môi giới chỉ được nhận tiền hoa hồng một lần duy nhất.

Khi bạn muốn mua một căn nhà, bạn phải trả tiền hoa hồng cho tất cả các môi giới đang phụ trách căn nhà đó. Nhiệm vụ của bạn là xác định số tiền tối thiểu cần phải trả nếu bạn muốn mua chính xác \(k\) căn nhà trong thành phố.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(m\), \(n\) và \(k\) - lần lượt là số lượng nhà, số lượng môi giới và số lượng nhà cần mua
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(l_i\), \(r_i\) và \(c_i\) - biểu thị khoảng nhà và tiền hoa hồng của môi giới thứ \(i\)

OUTPUT FORMAT:

• In ra một số duy nhất là số tiền tối thiểu cần phải trả để mua chính xác \(k\) căn nhà.

Ràng buộc:

• \(1 \leq m, n, k \leq 10^5\)
• \(1 \leq l_i \leq r_i \leq m\)
• \(1 \leq c_i \leq 10^9\)

Ví dụ

INPUT

10 3 4
1 2 100
5 10 5
7 8 10

OUTPUT

5

Giải thích

Chúng ta có thể mua các căn nhà có số \(5\), \(6\), \(9\), \(10\). Trong trường hợp này, chúng ta chỉ cần trả 5$ (trả cho môi giới thứ hai).