题目描述

FJ 开车去买 K 份食物送给咕噜，二者在同一直线上，相距 E 公里。若车上有 X 份食物，行驶每 1 公里花费 X 元（运输费用随载量线性变化）。
这条直线上有 N 个商店，第 i 个商店位于坐标 Xi（同一点可有多个商店），该店有 Fi 份食物，每份价格 Ci 元。
FJ 从位置 0 出发、只能向右走到位置 E（不能回头）。求把恰好 K 份食物送到目的地的购买费用 + 运输费用的最小值。

输入格式

• 第 1 行：三个整数 K, E, N
  (1 ≤ K ≤ 100, 1 ≤ E ≤ 350, 1 ≤ N ≤ 100)
• 第 2 行到第 N+1 行：每行三个整数 Xi, Fi, Ci
  (0 < Xi < E, 1 ≤ Fi ≤ 100, 1 ≤ Ci ≤ 10^6)

输出格式

输出一个整数：购买与运输总费用的最小值。

输入样例 #1

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

输出样例 #1

7

题目说明

在位置 3 与 4 各买 1 份食物：购买费用 2 + 2 = 4；
行驶时携带的食物数量导致的运输费用为 1 + 2 = 3；
总费用 4 + 3 = 7。