Farmer John đi quanh hội chợ lấy giải và xem biểu diễn dễ dàng, nhưng bò kiệt sức sau cả ngày. Ông sắp xếp xe tải đưa chúng giữa các nơi để tận hưởng hội chợ.

Xe tốt quá đắt, nên xe thuê chỉ chạy tuyến một lần (!) với $N$ trạm ($1 \le N \le 20{,}000$), số $1,\ldots,N$. Có $K$ nhóm ($1 \le K \le 50{,}000$), số $1,\ldots,K$, muốn đi. Mỗi trong $M_i$ bò nhóm $i$ ($1 \le M_i \le N$) muốn từ $S_i$ ($1 \le S_i<E_i$) tới $E_i$ phía sau trên tuyến ($S_i<E_i\le N$).

Sức chứa có thể không cho đón cả nhóm nhưng có thể đón một phần.

Với sức chứa $C$ ($1 \le C \le 100$) và mô tả nhóm, tìm số bò đi xe lớn nhất.

Dữ liệu vào

• Dòng $1$: số nguyên $K$, $N$, $C$ cách nhau bằng dấu cách.

• Dòng $2,\ldots,K+1$: dòng $i+1$ mô tả nhóm $i$ bằng số nguyên $S_i$, $E_i$, $M_i$ cách nhau bằng dấu cách.

Dữ liệu ra

• Dòng $1$: số bò đi xe lớn nhất.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

10

Ghi chú

Xe đón $2$ từ $1$ đến $5$, $3$ từ $5$ đến $8$, $2$ từ $8$ đến $14$, $1$ từ $9$ đến $12$, $1$ từ $13$ đến $14$, $1$ từ $14$ đến $15$.

Tác giả bài toán: Russ Cox và Hal Burch, 2006