题目描述

FJ 开车去买 $K$ 份食物，如果他的车上有 $X$ 份食物。每走一里就花费 $X$ 元。FJ 的城市是一条线，总共 $E$ 里路，有 $E+1$ 个地方，标号 $0\sim E$。 FJ 从 $0$ 开始走，到 $E$ 结束（不能往回走），要买 $K$ 份食物。 城里有 $N$ 个商店，每个商店的位置是 $X_i$（一个点上可能有多个商店），有 $F_i$ 份食物，每份 $C_i$ 元。 问到达 $E$ 并买 $K$ 份食物的最小花费。

输入格式

• 第一行：三个整数 $K$，$E$ 和 $N$，$1\leq K \leq 100$，$1\leq E \leq 350$，$1\leq N \leq 100$；
• 第二行到第 $N + 1$ 行：第 $i + 1$ 行有三个整数 $X_i$，$F_i$ 和 $C_i$，$0 < X_i < E$，$1\leq F_i \leq 100$，$1\leq C_i \leq 10^6$。

输出格式

单个整数，表示购买个运送饲料的最小费用之和。

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

7

提示

在离家较近的两家商店里各购买一吨饲料，则花费路上的钱是1+2=3，花在店里的钱是 2+2=4。