题目描述

公交车一共经过$\red{N（}$$\red{1<=N<=20000）}$个站点，从站点$\red{1}$一直驶到站点$\red{N}$。$\red{K（}$$\red{1<=K<=50000)}$群奶牛希望搭乘这辆公交车。

第$\red{i}$群牛一共有$\red{Mi（}$$\red{1<=Mi<=N)}$只.他们希望从$\red{Si}$到$\red{Ei}$去。

公交车只能座$\red{C（}$$\red{1<=C<=100）}$只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛听要求。

注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。

输入格式

第$\red{1}$行： 三个整数： $\red{K，}$$\red{N，}$$\red{C}$。 由空格隔开。

第$\red{2..K+1}$行：第$\red{i+1}$行，告诉你第$\red{i}$组奶牛的信息： $\red{S_i, E_i}$和 $\red{M_i}$。由空格隔开。

输出格式

第一行：可以在庙会乘坐捷运的牛的最大头数

样例

输入样例

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

输出样例

10

提示

捷运可以把$\red{2}$头奶牛从展台$\red{1}$送到展台$\red{5，}$$\red{3}$头奶牛从展台$\red{5}$到展台$\red{8，}$ $\red{2}$头奶牛从展台$\red{8 }$到展台$\red{14，}$$\red{1}$头奶牛从展台$\red{9}$送到展台$\red{12，}$一头奶牛从展台$\red{13}$送到展台$\red{14，}$ 一头奶牛从 $\red{14}$送到$\red{15}$。