题目描述

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

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

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

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

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

输入格式

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

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

输出格式

样例

输入样例

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

输出样例

7

提示

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