题目描述

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$。 第二行到第 $N+1$ 行，每行有三个整数 $Xi$ , $Fi$ 和 $Ci$。

输出格式

一个整数表示最小花费。

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

7

提示

1<=K，N<=100，1<=E<=350。 0<Xi<E，1<=Fi<=100，1<=Ci<=$10^6$。