题目描述

FJ 开车去买 K(1≤K≤100) 份食物。如果他的车上有 X 份食物，每走一里就花费 X 元。FJ 的城市是一条线，总共 E(1≤E≤350) 里路，有 E+1 个地方，标号 0~E。FJ 从 0 开始走，到 E 结束（不能往回走），要买 K 份食物。城里有 N(1≤N≤100) 个商店，每个商店的位置是 Xi(0<Xi<E)，有 Fi(1≤Fi≤100) 份食物，每份 Ci(1≤Ci≤1000000) 元。问到达 E 并买 K 份食物的最小花费。

输入格式

第 1 行：K,E,N。

第 2~N+1 行：Xi,Fi,Ci。

输出格式

一个正整数，为最小花费。

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

7

提示

样例解释：在离家较近的两家商店里各购买一份饲料，则花在路上的钱是 1 + 2 = 3，花在店里的钱是 2 + 2 = 4。

数据范围：1≤K≤100，1≤E≤350，1≤N≤100，0<Xi<E，1≤Fi≤100，1≤Ci≤1000000。

本题共 10 个测试点。

来源