P2616 [USACO10JAN] Buying Feed, II S

FJ 开车来到镇上，他要带 $K$ 吨饲料回家。运送饲料是需要花钱的，如果他的车上有 $X$ 吨饲料，开车 $D$ 公里就需要 $D×X$ 元。FJ 可以从 $N$ 家商店购买饲料，所有商店都在一个坐标轴上，第 $i$ 家店的位置是 $X_i$，饲料的售价为每吨 $C_i$ 元，库存为 $F_i$。 这个镇上有 $N(1 \le N \le 100)$ 家商店（编号为 $1 \sim N$）售卖饲料，所有商店都在一个长度为 $E(1 \le E \le 350)$ 的 $X$ 轴上。第 $i$ 个商店位于数轴上 $X_i$ 的位置，最多可以售卖给 FJ $F_i(1 \le F_i \le 100)$ 吨饲料，花费为 $C_i(1 \le C_i \le 10^6)$ 元每吨。奇妙的是，$X$ 轴上同一个坐标可能不只有一家商店。 FJ 从坐标为 $0$ 的地方出发并且只能向前走，直到到达坐标为 $E$ 的地方，并且需要买到 $K$ 吨饲料。他可以在沿途任意一家商店停下来买饲料。 请你求出 FJ 购买并运输 $K$ 吨饲料的最小花费是多少。

- 第一行：三个整数 $K$，$ E $ 和 $ N $，$ 1\leq K \leq 100 $，$ 1\leq E \leq 350 $，$ 1\leq N \leq 100 $； - 第二行到第 $ N + 1 $ 行：第 $ i + 1 $ 行有三个整数 $ X_i $，$ F_i $ 和 $ C_i $，$0 < X_i < E $，$1\leq F_i \leq 100 $，$1\leq C_i \leq 10^6$。

一个整数，表示购买并运送饲料的最小花费。

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