[Usaco2010 Jan]Buying Feed, II

农夫约翰需要购买至少 $K$ 磅饲料，并将其运送到目的地。

整个城市可以看作数轴上从 $0$ 到 $E$ 的一段。农夫约翰从位置 $0$ 出发，只能沿数轴正方向行驶，最终到达位置 $E$ 。如果他的车上装有 $W$ 磅饲料，那么行驶 $D$ 英里需要花费 $D\times W$ 美分。

沿途共有 $N$ 家商店，编号为 $1$ 到 $N$ 。第 $i$ 家商店位于位置 $X_i$ ，最多可以出售 $F_i$ 磅饲料，每磅饲料的价格为 $C_i$ 美分。同一位置可能有多家商店。农夫约翰可以在经过商店时购买不超过该商店库存的任意数量饲料。

请计算农夫约翰到达位置 $E$ 且购买了至少 $K$ 磅饲料时，购买和运输饲料所需的最小总费用。保证存在可行方案。

输入格式

第一行包含三个整数 $K,E,N$ ，分别表示需要购买的饲料数量、目的地的位置和商店数量。

接下来 $N$ 行，每行包含三个整数 $X_i,F_i,C_i$ ，分别表示第 $i$ 家商店的位置、库存量和每磅饲料的价格。

输出一个整数，表示购买和运输饲料所需的最小总费用，单位为美分。

最优方案是在位置 $3$ 和位置 $4$ 的商店各购买 $1$ 磅饲料，购买费用为 $2+2=4$ 美分。

从位置 $3$ 行驶到位置 $4$ 时，车上有 $1$ 磅饲料，运输费用为 $1\times 1=1$ 美分；从位置 $4$ 行驶到位置 $5$ 时，车上有 $2$ 磅饲料，运输费用为 $1\times 2=2$ 美分。

因此最小总费用为 $4+1+2=7$ 美分。

本题为 USACO 2010 January 试题「Buying Feed, II」，题面与测试数据整理自 BZOJ。