UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2059. [Usaco2010 Nov]Buying Feed 购买饲料

Statistics 下载数据

Description

  约翰开车来到镇上,他要带K吨饲料回家。运送饲料是需要花钱的,如果他的车上有X吨饲料,每公里就要花费X^2元,开车D公里就需要D* X^2元。约翰可以从N家商店购买饲料,所有商店都在一个坐标轴上,第i家店的位置是Xi,饲料的售价为每吨Ci元,库存为Fi。
    约翰从坐标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元。

Input

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

Output

一个整数,代表最小花费

Sample Input

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

Sample Output

9

Hint

Source

Gold