说明

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

输入格式

第一行三个数N，M，R

接下来M 行，每行三个数li，ri，wi

输出格式

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

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,

Source