问题 25256 --挤奶

25256: 挤奶

时间限制: 1 Sec  内存限制: 128 MB
提交: 105  解决: 26
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][13588kb]

题目描述

又到了产奶季节,贝茜决定在接下来的N个小时里让FJ挤奶。贝茜的牛奶不是什么时候都能挤的……贝茜规定了M个时间段可以挤奶,每个时间段表示为liri,在这一时间挤奶可以得到wi的牛奶贝茜每次挤奶后都要休息R个小时,FJ想知道,最多能挤多少奶?

输入

第一行三个数NMR

接下来M 行,每行三个数liriwi

输出

一个数,表示最大的挤奶量。

样例输入

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

样例输出

43

提示


对于30%的数据,N<=100,M<=20



对于100%的数据,N<=1000000,M<=100000,0<=R<=N,1<=li<=ri<=N,


Wi<=10000

来源

[提交][状态]