Có \(N\) điểm trên một con đường thẳng, được đánh số \(1,2,\ldots,N\) từ trái sang phải. Con đường chỉ cho phép đi một chiều từ trái sang phải. Ngoài ra, có \(M\) máy dịch chuyển được đánh số từ \(1\) đến \(M\); máy \(i\) (\(1 \le i \le M\)) đưa người sử dụng từ điểm \(S_i\) đến điểm \(T_i\), với \(S_i<T_i\).

Bitaro hiện ở điểm \(1\) và muốn đến điểm \(N\). Khi ở điểm \(j\) (\(1 \le j \le N-1\)), cậu có thể đi bộ đến điểm \(j+1\), hoặc chọn một máy \(i\) thỏa \(S_i=j\) để dịch chuyển đến điểm \(T_i\).

Việc dịch chuyển gây áp lực lên cơ thể. Lo lắng cho sự an toàn của Bitaro, bạn quyết định lựa chọn những máy dịch chuyển cần phá hủy (có thể không chọn máy nào) sao cho bất kể cậu chọn đường đi nào, số lần dịch chuyển đều không quá \(K\). Phá hủy máy \(i\) tốn chi phí \(C_i\); sau khi bị phá hủy, máy đó không còn sử dụng được.

Hãy tìm tổng chi phí nhỏ nhất để phá hủy các máy và bảo đảm yêu cầu trên mọi đường đi của Bitaro.

Dữ liệu vào

Dòng đầu gồm \(N,M,K\). \(M\) dòng tiếp theo, dòng \(i\) gồm \(S_i,T_i,C_i\).

Dữ liệu ra

In chi phí nhỏ nhất cần trả.

Ràng buộc

• \(2\le N\le100000\).
• \(1\le K\le M\le100000\).
• \(1\le S_i<T_i\le N\).
• \(1\le C_i\le10^9\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(K=1\).
2. \(3\) điểm: \(N,M\le20\).
3. \(29\) điểm: \(N,M\le500\).
4. \(23\) điểm: \(N,M\le4000\).
5. \(24\) điểm: \(N,M\le40000\).
6. \(16\) điểm: không có ràng buộc thêm.

Ví dụ

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

4

12 7 2
1 5 3
4 8 2
2 4 5
2 4 8
7 9 4
9 11 7
3 10 5

6

6 3 2
1 4 2
2 5 4
3 6 3

0

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 2, bài Teleporter 2, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.