题目描述

贝西是一头勤劳的奶牛。她非常专注于最大化她的生产力，以至于她决定安排她的下一个N(1≤N≤1,000,000)小时(方便地标记为0..N-1)，以便她生产尽可能多的牛奶。
农民约翰有一个包含M(1≤M≤1000)个可能重叠的时间间隔的列表，在这些时间间隔中他可以挤奶。每个间隔i都有一个起始时间(0≤starting_houri≤N)，一个结束时间(starting_houri < ending_houri≤N)，以及对应的加仑牛奶(1≤efficienci≤1,000,000)，表示在该间隔内他能从贝西身上得到多少加仑牛奶。奶牛产奶后需要休息R小时才能继续下一次产奶，求贝西最大的挤奶量。

输入格式：

第一行:三个空格分隔的整数:N、M和R
第2行 . .M+1:第i+1行用三个空格分隔的整数:starting_houri, ending_houri和efficiencyi来描述约翰的一次挤奶间隔。

输出格式：

第一行:贝西在N小时内能生产的最大牛奶加仑数

输入样例#1：

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

输出样例#1：

43