You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

农夫约翰需要前往镇上采购(K)（(1\leq K\leq100)）磅饲料。他驾驶卡车运输(K)磅饲料行驶(D)英里的成本是(D\times K)美分。

县城的饲料场有(N)（(1\leq N\leq100)）家商店（方便起见编号为(1)到(N)）出售饲料。每家商店都位于长度为(E)（(1\leq E\leq350)）的(X)轴线段上。商店(i)位于数轴上的位置(X_i)（(0\lt X_i\lt E)）处，最多能以每磅(C_i)（(1\leq C_i\leq1000000)）美分的价格卖给约翰(F_i)（(1\leq F_i\leq100)）磅饲料。令人惊讶的是，(X)轴上的一个给定点可能有不止一家商店。

约翰从数轴上的位置(0)出发，只能沿正方向行驶，最终到达位置(E)，且至少要携带(K)磅饲料。他可以在沿途的任何一家饲料店停下来，购买不超过该店存货上限的任意数量的饲料。

约翰购买并运输(K)磅饲料所需支付的最小金额是多少？约翰知道一定有解决方案。

考虑这样一个示例，约翰需要从数轴上(0)到(5)区间内的三家商店（位置分别为(1)、(3)和(4)）购买两磅饲料：

0   1   2   3   4   5 
+---|---+---|---|---+ 
    1       1   1      可购买的饲料磅数 
    1       2   2      每磅饲料的价格（美分） 

对约翰来说，最好的方案是从第二家和第三家商店各买一磅饲料。他每买一磅饲料需支付(2)美分，所以购买饲料的总成本是(4)美分。当约翰从位置(3)行驶到位置(4)时，行驶距离为(1)单位长度，他携带(1)磅饲料，所以需支付(1\times1 = 1)美分。

当约翰从位置(4)行驶到位置(5)时，行驶距离为(1)单位长度，他携带(2)磅饲料，所以需支付(1\times2 = 2)美分。

总成本为(4 + 1 + 2 = 7)美分。

输入格式

• 第一行：三个整数K，E 和N，1 ≤ K ≤ 100, 1 ≤ E ≤ 350, 1 ≤ N ≤ 100

• 第二行到第N + 1 行：第i + 1 行有三个整数$X_i$，$F_i 和C_i$，$0 < X_i < E; 1 ≤ F_i ≤ 100; 1 ≤C_i ≤ 10^6$

输出格式

单个整数：表示购买和运送饲料的最小费用之和

样例 #1

样例输入 #1

2 5 3
3 1 2
4 1 2
1 1 1

样例输出 #1

7

样例解释：

在离家较近的两家商店里各购买一吨饲料，则花在路上的钱是1 + 2 = 3，花在店里的钱是2 + 2 = 4