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

Trong một buổi thảo luận về chiến lược kinh doanh, FullHouse Dev được yêu cầu phát triển một tính năng tối ưu chi phí môi giới bất động sản.

Bài toán

Trong thành phố có \(N\) môi giới bất động sản. Có một con đường với \(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 phí môi giới là \(C_i\) đô la.

Lưu ý: Mỗi môi giới sẽ được trả phí môi giới là \(C_i\) đô la.

Khi bạn muốn mua một căn nhà, bạn phải trả phí môi giới cho tất cả các môi giới đang phụ trách căn nhà đó, nhưng mỗi môi giới chỉ được trả phí một lần.

Nhiệm vụ của bạn là xác định số tiền tối thiểu (tính bằng đô la) cần phải trả khi muốn mua chính xác \(K\) căn nhà trong thành phố.

INPUT FORMAT:

• Dòng đầu tiên: Ba số nguyên \(M\), \(N\) và \(K\) cách nhau bởi dấu cách, 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 gồm ba số nguyên \(L_i\), \(R_i\) và \(C_i\) cách nhau bởi dấu cách, biểu thị phạm vi nhà và phí môi giới của môi giới thứ \(i\)

OUTPUT FORMAT:

Một dòng duy nhất chứa một số nguyên biểu thị 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ỉ phải trả 5$ (trả cho môi giới thứ hai).