[USACO10NOV] Buying Feed G

题目描述

约翰开车来到镇上，他要带 $K$ 吨饲料回家。

运送饲料是需要花钱的，如果他的车上有 $X$ 吨饲料，每公里就要花费 $X^2$ 元，开车D公里就需要 $D \times X^2$ 元。

约翰可以从 $N$ 家商店购买饲料，所有商店都在一个坐标轴上，第 $i$ 家店的位置是 $X_i$ ，饲料的售价为每吨 $C_i$ 元，库存为 $F_i$ 。

约翰从坐标 $X=0$ 开始沿坐标轴正方向前进，他家在坐标 $X=E$ 上。

为了带 $K$ 吨饲料回家，约翰最少的花费是多少呢？

假设所有商店的库存之和不会少于 $K$ 。

举个例子，假设有三家商店，情况如下所示：

坐标	$X=1$	$X=3$	$X=4$	$E=5$
库存	$1$	$1$
售价	$1$	$2$

如果 $K=2$ ，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是 $1+4=5$ ，花在商店的钱是 $2+2=4$ ，共需要 $9$ 元。

第一行三个整数 $K,E,N$ （$1 \leq K \leq 10^4 , 1 \leq E \leq 500 , 1 \leq N \leq 500$）

下来 $N$ 行，每行三个整数 $X_i \ F_i \ C_i$ ( $0 < Xi < E,1 \leq Fi \leq 10^4,1 \leq C_i \leq 10^7$ ）。

一个整数，代表最小花费