题目描述

农夫约翰需要到镇上去取 $\red{K (1 <= K <= 100) }$磅的饲料。在他的卡车上用 $\red{K }$磅饲料行驶 $\red{D }$英里需要 $\red{D\times K }$美分。

县饲料厂有 $\red{N (1 <= N <= 100) }$家商店（方便地编号为 $\red{1..N）}$出售饲料。每个商店都位于长度为 $\red{E (1 <= E <= 350) }$的 $\red{X }$轴段上。商店 $\red{i }$位于数轴上的位置 $\red{X_i (0 < X_i < E)，}$并且可以以 $\red{C_i (1 <= C_i <= 1,000,000) }$的成本销售 $\red{FJ }$和 $\red{F_i (1 <= F_i <= 100) }$磅饲料$\red{) }$美分每磅。

令人惊讶的是，$\red{X }$轴上的给定点可能有多个商店。$\red{FJ }$从该数轴上的位置 $\red{0 }$开始，只能沿正向行驶，最终到达位置 $\red{E，}$饲料至少为 $\red{K }$磅。他可以在沿途的任何一家饲料店停下来购买任何数量的饲料，直到商店的限额。$\red{FJ }$购买和运输 $\red{K }$磅饲料需要支付的最低金额是多少？

$\red{FJ }$知道有一个解决方案。考虑一个样本，其中 $\red{FJ }$需要来自三个商店（位置：$\red{1}$、$\red{3 }$和 $\red{4）}$的两磅饲料，其范围为 $\red{0..5：}$$\red{0 1 2 3 4 5 +---|---+ ---|---|---+ 1 1 1 }$可用饲料磅数 $\red{1 2 2 }$美分每磅 $\red{FJ }$最好从第二家和第三家商店购买一磅饲料。他必须支付 $\red{2 }$美分来购买每磅饲料，总成本为 $\red{4}$。当 $\red{FJ }$从 $\red{3 }$移动到 $\red{4 }$时，他移动 $\red{1 }$个单位长度并且他有 $\red{1 }$磅饲料，因此他必须支付 $\red{1\times 1 = 1 }$美分。当 $\red{FJ }$从 $\red{4 }$移动到 $\red{5 }$时，他移动了一个单位并且他有 $\red{2 }$磅饲料，所以他必须支付 $\red{1\times 2 = 2 }$美分。总成本为 $\red{4+1+2 = 7 }$美分。

$\red{FJ}$开车去买$\red{K}$份食物，如果他的车上有$\red{X}$份食物。每走一里就花费$\red{X}$元。 $\red{FJ}$的城市是一条线，总共$\red{E}$里路，有$\red{E+1}$个地方，标号$\red{0}$~$\red{E}$。 $\red{FJ}$从$\red{0}$开始走，到$\red{E}$结束（不能往回走），要买$\red{K}$份食物。 城里有$\red{N}$个商店，每个商店的位置是$\red{X_i（}$一个点上可能有多个商店），有$\red{F_i}$份食物，每份$\red{C_i}$元。 问到达$\red{E}$并买$\red{K}$份食物的最小花费

输入格式

第$\red{1}$行：$\red{K,E,N }$

第$\red{2\sim N+1}$行：$\red{X_i,F_i,C_i}$。

输出格式

样例

输入样例

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

输出样例

7

提示

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