激动人心的CSP第二轮比赛终于完赛了，小T心情不错，因为她的发挥着实不错，估算下来应该有三百好几十分，她很是感谢老师和同学给予的帮助，决定买一些礼物回来表达自己的谢意。
JS赛区在NJ比赛，从NJ回WJ的路上，总共有E里路，有E+1个地方，编号为0~E。
小T从NJ（0）出发，到WJ（E）结束（不能往回走），要买K份礼物。
沿路有N个商店，每个商店的位置是Xi（一个点上可能有多个商店），有Fi份商品，每份Ci元。
如果她的车上有X份礼物，每走一里路就要花费X元（油钱也是钱啊）。
问到达E并买K份礼物的最小花费是多少元？
第1行：三个空格分隔的整数：K、E和N
第2..N+1:行i+1包含三个空格分隔的整数：Xi、Fi和Ci
第1行：一个整数，是小T购买和运输礼物的最低成本。
2 5 3
3 1 2
4 1 2
1 1 1
7
100%的数据，1 ≤ K，N ≤ 100，1 ≤ E ≤ 350，0 < X_i
< E，1 ≤ F_i ≤ 100，1 ≤ C_i ≤ 1000000。