Giải bài trực tuyến

Mặc dù Farmer John không có khó khăn gì khi đi bộ quanh hội trợ để thu thập những thứ mong ước hoặc xem các gian trưng bầy, những con bò của anh ta không thực sự khỏe mạnh; nên sau cả một ngay đi bộ quanh hội trợ đã làm họ rất mệt. Để giúp chúng thích hội trợ, FJ đã sắp xếp một chuyến xe dẫn những chú bò từ địa điểm này đến địa điểm khác trong hội trợ.

FJ không có đủ tài chính để trả một chuyến đi quá dài, nên hành trình mà anh ta thêu đi qua các tuyến đường đú một lần. Có N điểm dừng trong hội trợ (1 <= N <= 20,000) (được đánh số từ 1 đến N) dọc theo tuyến đường của nó. Có tổng cộng K nhóm (1 <= K <= 50,000) bò được đánh số từ 1..K muốn đi hành trình đó, mỗi con trong M_i con bò (1 <= M_i <= N) trong nhóm i muốn đi từ điểm dừng S_i (1 <= S_i < E_i) tới điểm dừng khác E_i (S_i < E_i <= N) theo dọc hành trình đó.

Xe hành trình không thể mang toàn bộ nhóm của những chú bò vì bị giới hạn bởi tối đa được trở, nhưng ban có thể lấy một phân của các nhóm sao cho thích hợp.

Cho gới hạn tối đa được trở C (1 <= C <= 100) của xe và những miêu tả các nhóm bò mà muốn tham những điểm dừng khác nhau trong hội trợ, hay xác định số lượng con bò lớn nhất có thể đi tuyến xe trong hội trợ.

Dữ liệu

* Dòng một 1: Ba số nguyên được viết cách nhau: K, N, và C

* Dòng 2..K+1: Dòng i+1 miêu tả nhóm bò i bằng ba số nguyên dương được viết cách nhau : S_i, E_i, and M_i

Kết quả

* Dòng 1: Số lượng con bò lớn nhất có thểm đi tuyến xe ở hội trợ.

Ví dụ

Dữ liệu:

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

Kết quả :

10

Giải thích:

Xe có thể trở 2 con bò từ điểm dừng 1 đến điểm dừng 5, 3 từ 5 đến 8, 2 từ 8 đến 14, 1 từ 9 đến 12, 1 từ 13 đến 14, và 1 từ 14 đến 15.