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