题目描述

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

约翰从坐标${X=O}$开始沿坐标轴正方向前进，他家在坐标${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.}$

输出格式

一个整数,代表最小花费

样例

输入样例

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

输出样例

9