贝茜是一只努力产奶的奶牛。实际上，她很注意她的产奶量，所以她要在下面N(1<=N<=1,000,000)个小时(方便起见，标记为0..N-1)安排好产奶时间表，以使能产尽可能多的奶。

FJ在他挤奶的时间里，会有M(1<=M<=1,000)个可能重叠的时间段。每个时间段i是从开始时间(1<=starting_hour_i<N)，到一个结束时间(ending_hour_i<=1,000,000)，和一个相应的挤奶效率(1<=efficiency_i<=1,000,000)表示他在一个时间段可以挤多少加仑牛奶。FJ分别在开始时间和结束时间开始工作和结束工作。当正在挤奶时，贝茜必须一直在这段时间内产奶。

因此贝茜有她的产奶极限。在任何一次挤奶后，她必须休息R(1<=R<=N)小时，才能开始下次挤奶。根据给出的FJ的挤奶时间表，计算出贝茜可以在这N小时内产奶的最大值。

第一行：三个用空格隔开的整数N,M和R
第二行至第i+1行：用三个由空格隔开的整数描述FJ的挤奶时间表：开始时间i，结束时间i和效率i

第一行:贝茜可以在N小时内产出的最大加仑的牛奶.

输入样例解释:
贝茜想确定以下12个小时的产奶时间表;FJ有4个挤奶时间段;贝茜每次挤奶后必须休息2小时.第一挤奶时间是从小时1到小时2,第二次从小时10到小时12,第三次从小时3到小时6,第四次从小时7到小时10.FJ可以分别得到8,19,24,31加仑牛奶.

输出样例解释:
如果贝茜选择在第一时间段产奶,那么她不能在第三时间段产奶,因为她
要2个小时休息.如果她选择在第二时间段产奶,她就不能在第四时间段产
奶.最终,如果她在第三时间段产奶,她就不能在第四时间段产奶.最好的
方案是选择在第二和第三时间段产奶,共可以产43加仑牛奶.

补充说明：挤奶时间从s到e表示区间[s,e)，如果中途要休息R个时间段，则下一段时间s'>=e+R。