Farmer John camina por la feria a recoger premios y ver espectáculos sin problemas, pero las vacas se agotan tras un día. Ha preparado un camión lanzadera para llevarlas entre los lugares.

No puede pagar uno bueno, así que el alquilado recorre su ruta una sola vez (!) con $N$ paradas ($1 \le N \le 20{,}000$), numeradas $1,\ldots,N$. Hay $K$ grupos ($1 \le K \le 50{,}000$), numerados $1,\ldots,K$. Cada una de las $M_i$ vacas del grupo $i$ ($1 \le M_i \le N$) quiere ir de $S_i$ ($1 \le S_i<E_i$) a $E_i$ más adelante ($S_i<E_i\le N$).

La capacidad puede impedir llevar un grupo completo, pero puede llevar parte.

Dadas capacidad $C$ ($1 \le C \le 100$) y descripciones, encuentra el máximo de vacas que pueden viajar.

Entrada

• Línea $1$: enteros $K$, $N$, $C$ separados por espacios.

• Líneas $2,\ldots,K+1$: la línea $i+1$ describe grupo $i$ con enteros $S_i$, $E_i$, $M_i$ separados por espacios.

Salida

• Línea $1$: máximo de vacas que pueden viajar.

Ejemplos

Entrada 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

Salida 1

10

Nota

Puede llevar $2$ de $1$ a $5$, $3$ de $5$ a $8$, $2$ de $8$ a $14$, $1$ de $9$ a $12$, $1$ de $13$ a $14$ y $1$ de $14$ a $15$.

Autores del problema: Russ Cox y Hal Burch, 2006