Farmer John はお祭りを歩いて景品を集めたりショーを見たりできますが、牛は体力がなく一日歩くと疲れ果てます。楽しめるよう送迎トラックを用意しました。

よい車を借りる余裕がなく、借りた車は経路を 1 回だけ（！）走り、$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 年