Farmer John bez problemu chodzi po jarmarku po nagrody i na pokazy, lecz krowy po całym dniu są wyczerpane. Zorganizował ciężarówkę przewożącą je między miejscami.

Dobry pojazd jest za drogi, więc wynajęty jedzie trasą tylko raz (!) z $N$ przystankami ($1 \le N \le 20{,}000$), numerowanymi $1,\ldots,N$. Jest $K$ grup ($1 \le K \le 50{,}000$), numerowanych $1,\ldots,K$. Każda z $M_i$ krów grupy $i$ ($1 \le M_i \le N$) chce od $S_i$ ($1 \le S_i<E_i$) do późniejszego $E_i$ ($S_i<E_i\le N$).

Pojemność może nie pozwolić na całą grupę, ale można brać część.

Z pojemności $C$ ($1 \le C \le 100$) i opisów znajdź maksimum przewiezionych krów.

Wejście

• Wiersz $1$: całkowite $K$, $N$, $C$ rozdzielone spacjami.

• Wiersze $2,\ldots,K+1$: wiersz $i+1$ opisuje grupę $i$ całkowitymi $S_i$, $E_i$, $M_i$ ze spacjami.

Wyjście

• Wiersz $1$: maksymalna liczba jadących krów.

Przykład

Wejście 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

Wyjście 1

10

Uwagi

Można zabrać $2$ z $1$ do $5$, $3$ z $5$ do $8$, $2$ z $8$ do $14$, $1$ z $9$ do $12$, $1$ z $13$ do $14$ i $1$ z $14$ do $15$.

Autorzy zadania: Russ Cox i Hal Burch, 2006