Farmer John kann problemlos auf dem Jahrmarkt Preise sammeln und Vorstellungen sehen, aber seine Kühe sind nach einem Tag erschöpft. Damit sie den Jahrmarkt genießen können, organisiert er einen Shuttle-Lkw zwischen den Orten.

Ein guter ist zu teuer, daher fährt der gemietete seine Route nur einmal (!) mit $N$ Haltestellen ($1 \le N \le 20{,}000$), nummeriert $1,\ldots,N$. $K$ Gruppen ($1 \le K \le 50{,}000$), nummeriert $1,\ldots,K$, wollen mit. Jede der $M_i$ Kühe in Gruppe $i$ ($1 \le M_i \le N$) will von $S_i$ ($1 \le S_i<E_i$) nach späterem $E_i$ ($S_i<E_i\le N$).

Kapazität kann ganze Gruppen verhindern, aber Teile dürfen mitfahren.

Bestimme aus Kapazität $C$ ($1 \le C \le 100$) und Gruppen die maximale Zahl mitfahrender Kühe.

Eingabe

• Zeile $1$: ganze Zahlen $K$, $N$, $C$, durch Leerzeichen getrennt.

• Zeilen $2,\ldots,K+1$: Zeile $i+1$ beschreibt Gruppe $i$ durch ganze Zahlen $S_i$, $E_i$, $M_i$ mit Leerzeichen.

Ausgabe

• Zeile $1$: maximale Zahl mitfahrender Kühe.

Beispiele

Eingabe 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

Ausgabe 1

10

Hinweis

Es fahren $2$ von $1$ nach $5$, $3$ von $5$ nach $8$, $2$ von $8$ nach $14$, $1$ von $9$ nach $12$, $1$ von $13$ nach $14$ und $1$ von $14$ nach $15$.

Autoren der Aufgabe: Russ Cox und Hal Burch, 2006