[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$ 售价|$1$|$2$|$2$ 如果$K=2$,约翰的最优选择是在离家较近的两家商店购买饲料,则花在路上的钱是$1+4=5$,花在商店的钱是$2+2=4$,共需要$9$元。

输入输出格式

输入格式


第$1$行:三个整数$K,E,N$ 第$2..N+1$行:第$i+1$行的三个整数代表,$X_i,F_i,C_i$.

输出格式


一个整数,代表最小花费

输入输出样例

输入样例 #1

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

输出样例 #1

9

说明

$1 \leq K \leq 10000 , 1 \leq E \leq 500 , 1 \leq N \leq 500$ $0 < Xi < E, 1 \leq Fi \leq 10000, 1 \leq C_i \leq 10^7$