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