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

题目描述

农夫约翰需要前往镇上采购(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