该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

植树节快到了，Hacker 想要多种植一些树木，绿化大地。

于是他打算在长度为$L$的道路两旁每隔$M$米种植一棵树，正常情况下他种一棵树需要25分钟，但是由于有部分位置的土壤质地不一样，所以 Hacker 种树的时间有时会和正常情况不一样，质地软的就种得快，质地硬的就种得慢，当然不一样的土壤是预先知道的。但是由于时间的变化，土地质地也是在发生变化，所以给出的土壤的检查报告也是会不停的更新，我们应当使用最新的报告数据，如果没有新的报告，则证明原土地质地未发生改变。

Hacker 想统计他种完一条路上的树需要多少时间。

道路起始位置为0，起始位置当然也是要植树的。

注意道路的两边都要植树。

输入格式

第1行三个整数依次对应$L, M, N，L$表示道路有$L$米，$M$表示两棵树之间的间距为$M$米，$N$表示有$N$份土壤的检查报告;

第2~$N$+1行，为当前最新检测报告，每行3个整数$X, Y, K$，从第$X$米开始到$Y$米结束这段道路的质地是一样的，在这些地上每种树需要耗费 K分钟时间

输出格式

一个整数，表示 Hacker 种完一条道路上的树需要的总时间。

结果可能较大，不过不用担心 Hacker 累死哦！他是Superman

样例

25  5   4
5  10 15
11 15 25
15 25 35
16 22 16

282

样例1解释

这条道路长度为25米，每隔5米种植一棵树，有4份土壤检测报告；

报告1：5~10这段区间，一棵树木种植时间为15分钟；

报告2：11~15这段区间，一棵树木种植时间为25分钟；

报告3：15~25这段区间，一棵树木种植时间为35分钟；

报告4：16~22这段区间，一棵树木种植时间为16分钟；

树木种植点位为：0,5,10,15,20,25

而这些点位对应的树木种植时间分别为：25,15,15,35,16,35分钟

共需要时间：2*(25+15+15+35+16+35)=282分钟。

960 203 8
66  66  182
32  32  259
480 605 972
858 858 157
294 617 545
169 420 878
182 521 650
511 511 711

3790

数据范围

对于 100% 的数据：$1 ≤ L,M,N,K ≤ 1000, 0 ≤ X ≤ Y ≤ 1000$