Farmer John 在集市逛着领奖看演出毫无困难，但牛的体力不够，走一整天就筋疲力尽。为了让牛享受集市，他安排接驳卡车送她们到各处。

他租不起好车，租来的接驳车只跑一遍路线（！），沿途有 $N$ 站（$1 \le N \le 20{,}000$），编号 $1,\ldots,N$。共有 $K$ 群牛（$1 \le K \le 50{,}000$），编号 $1,\ldots,K$，想乘车。群 $i$ 的 $M_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$ 行用以空格分隔的整数 $S_i$、$E_i$、$M_i$ 描述群 $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 年