题目描述

约翰开车来到镇上，他要带$\red{K}$吨饲料回家。运送饲料是需要花钱的，如果他的车上有$\red{X}$吨饲料，每公里就要花费$\red{X^2}$元，开车$\red{D}$公里就需要$\red{D\times X^2}$元。约翰可以从$\red{N}$家商店购买饲料，所有商店都在一个坐标轴上，第$\red{i}$家店的位置是$\red{X_i，}$饲料的售价为每吨$\red{C_i}$元，库存为$\red{F_i}$。

约翰从坐标$\red{X=O}$开始沿坐标轴正方向前进，他家在坐标$\red{X=E}$上。为了带$\red{K}$吨饲料回家，

约翰最少的花费是多少呢？假设所有商店的库存之和不会少于$\red{K}$。

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

坐标 $\red{X=1 ~ ~~~X=3 ~ ~~~ X=4 ~~ ~~E=5}$

库存 $\red{ ~~~~~1 ~~~ ~~~~~ ~~~~~ 1 ~~~ ~~~~~ ~~~~~ 1}$

售价 $\red{ ~~~~~1 ~~~ ~~~ ~~~~~~~ 2 ~~~ ~~~~~ ~~~~~ 2}$

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

输入格式

第$\red{1}$行:三个整数$\red{K,E,N }$

第$\red{2..N+1}$行:第$\red{i+1}$行的三个整数代表,$\red{X_i,F_i,C_i.}$

输出格式

一个整数,代表最小花费

样例

输入样例

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

输出样例

9