1331: 学习时间问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：7
题目描述
小明是一个好学的孩子，他学习的时候总能达到最高的学习效率，这是因为他每次做作
业是都会安排他做作业的N(1<=N<=1000000)个小时，使得完成的作业量尽可能多。
小明有个时间安排表，包含M(1<=M<=1000)个安排用来学习的时间段，这些时间段可
能重叠。每个时间段i 有一个开始时间start_hour(0<=start_hourend_hour(start_hour能完成的作业量。小明每次从开始时间开始学习到结束时间结束。
但是小明也会累，他也需要休息，每次学习之后，他都要休息R(1<=R<=N)个小时，然
后才能开始新一时间段的学习。给出小明每个时间段的学习量，你的任务是求在这N 个小
时中小明能完成的最大作业量。
业是都会安排他做作业的N(1<=N<=1000000)个小时，使得完成的作业量尽可能多。
小明有个时间安排表，包含M(1<=M<=1000)个安排用来学习的时间段，这些时间段可
能重叠。每个时间段i 有一个开始时间start_hour(0<=start_hour
但是小明也会累，他也需要休息，每次学习之后，他都要休息R(1<=R<=N)个小时，然
后才能开始新一时间段的学习。给出小明每个时间段的学习量，你的任务是求在这N 个小
时中小明能完成的最大作业量。
输入
第一行：三个整数，N,M,R
接下来M 行，每行给出一个时间段的描述，由三个整数组成，分别是开始时间，结束时
间，还有这个时间段的学习量。
接下来M 行，每行给出一个时间段的描述，由三个整数组成，分别是开始时间，结束时
间，还有这个时间段的学习量。
输出
输出小明在这N 个小时的最大学习量。
样例输入 复制
12 4 2
1 2 8
10 12 19
3 6 24
7 10 31样例输出 复制
43提示
最优的方案是选择10-12 和3-6 两个时间段学习，完成学习量为43.