Mặc dù Farmer John không có khó khăn gì khi đi bộ quanh hội chợ để thu thập giải thưởng hoặc xem các gian trưng bày, những con bò của anh ta không khỏe mạnh như thế; một ngày đi bộ quanh hội chợ đã làm chúng rất mệt. Để giúp chúng có thể tận hưởng hội chợ, 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 chợ.

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

Vì bị giới hạn sức chứa, chuyến xe có thể không có khả năng chở theo toàn bộ một nhóm bò nào đó, nhưng bạn có thể chỉ chở một phần của nhóm đó.

Cho biết sức chứa ~C~ ~(1 \le C \le 100)~ của xe và các nhóm bò, hãy xác định số lượng con bò lớn nhất có thể đi chuyến xe.

Input

• Dòng ~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~.

Output

• Dòng ~1~: Số lượng con bò lớn nhất có thể đi chuyến xe.

Sample Input

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

Sample Output

10

Note

Xe có thể chở:

• ~2~ con bò từ điểm dừng ~1~ đến điểm dừng ~5~
• ~3~ con bò từ điểm dừng ~5~ đến điểm dừng ~8~
• ~2~ con bò từ điểm dừng ~8~ đến điểm dừng ~14~
• ~1~ con bò từ điểm dừng ~9~ đến điểm dừng ~12~
• ~1~ con bò từ điểm dừng ~13~ đến điểm dừng ~14~
• ~1~ con bò từ điểm dừng ~14~ đến điểm dừng ~15~