يتجول Farmer John في المعرض لجمع الجوائز ومشاهدة العروض بسهولة، لكن الأبقار تنهك بعد يوم كامل. وفر شاحنة لنقلها بين المواقع لتستمتع.

لم يستطع دفع ثمن جيدة، فالمستأجرة تسير المسار مرة واحدة فقط (!) ولها $N$ محطات ($1 \le N \le 20{,}000$)، مرقمة $1,\ldots,N$. تريد $K$ مجموعات ($1 \le K \le 50{,}000$)، مرقمة $1,\ldots,K$، الركوب. كل من $M_i$ أبقار المجموعة $i$ ($1 \le M_i \le N$) تريد من $S_i$ ($1 \le S_i<E_i$) إلى $E_i$ لاحقًا ($S_i<E_i\le N$).

قد تمنع السعة نقل مجموعة كاملة، لكن يمكن نقل جزء منها.

مع السعة $C$ ($1 \le C \le 100$) ووصف المجموعات أوجد أكبر عدد أبقار يمكن نقلها.

الإدخال

• السطر $1$: الأعداد الصحيحة $K$ و$N$ و$C$ بفراغات.

• الأسطر $2,\ldots,K+1$: يصف السطر $i+1$ المجموعة $i$ بالأعداد الصحيحة $S_i$ و$E_i$ و$M_i$ بفراغات.

الإخراج

• السطر $1$: أكبر عدد أبقار يمكنها الركوب.

أمثلة

الإدخال 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

الإخراج 1

10

ملاحظة

يمكن نقل $2$ من $1$ إلى $5$، و$3$ من $5$ إلى $8$، و$2$ من $8$ إلى $14$، و$1$ من $9$ إلى $12$، و$1$ من $13$ إلى $14$، و$1$ من $14$ إلى $15$.

مؤلفا المسألة: Russ Cox وHal Burch، 2006