Farmer John peut marcher dans la foire pour recevoir des prix et voir les spectacles, mais ses vaches s’épuisent après une journée. Il organise un camion-navette pour les transporter entre les lieux.

Il ne peut payer une bonne navette : celle louée ne parcourt sa route qu’une fois (!), avec $N$ arrêts ($1 \le N \le 20{,}000$), numérotés $1,\ldots,N$. $K$ groupes ($1 \le K \le 50{,}000$), numérotés $1,\ldots,K$, veulent monter. Chacune des $M_i$ vaches du groupe $i$ ($1 \le M_i \le N$) va de $S_i$ ($1 \le S_i<E_i$) à $E_i$ plus loin ($S_i<E_i\le N$).

La capacité peut empêcher de prendre un groupe entier, mais on peut en prendre une partie.

Avec la capacité $C$ ($1 \le C \le 100$) et les groupes, trouvez le maximum de vaches transportées.

Entrée

• Ligne $1$ : entiers $K$, $N$, $C$ séparés par des espaces.

• Lignes $2,\ldots,K+1$ : la ligne $i+1$ décrit le groupe $i$ par les entiers $S_i$, $E_i$, $M_i$ séparés par des espaces.

Sortie

• Ligne $1$ : nombre maximal de vaches transportées.

Exemples

Entrée 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

Sortie 1

10

Remarque

On peut prendre $2$ de $1$ à $5$, $3$ de $5$ à $8$, $2$ de $8$ à $14$, $1$ de $9$ à $12$, $1$ de $13$ à $14$ et $1$ de $14$ à $15$.

Auteurs du problème : Russ Cox et Hal Burch, 2006