题目描述

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

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

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

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

输入格式

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

第${2..K+1}$行：第${i+1}$行，告诉你第${i}$组奶牛的信息： ${S_i, E_i}$和 ${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

提示

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