题目描述

FJ 开车来到镇上，他要带 $K$ 吨饲料回家。运送饲料是需要花钱的，如果他的车上有 $X$ 吨饲料，开车 $D$ 公里就需要 $D×X$ 元。FJ 可以从 $N$ 家商店购买饲料，所有商店都在一个坐标轴上，第 $i$ 家店的位置是 $X_i$，饲料的售价为每吨 $C_i$ 元，库存为 $F_i$。

这个镇上有 $N(1 \le N \le 100)$ 家商店（编号为 $1 \sim N$）售卖饲料，所有商店都在一个长度为 $E(1 \le E \le 350)$ 的 $X$ 轴上。第 $i$ 个商店位于数轴上 $X_i$ 的位置，最多可以售卖给 FJ $F_i(1 \le F_i \le 100)$ 吨饲料，花费为 $C_i(1 \le C_i \le 10^6)$ 元每吨。奇妙的是，$X$ 轴上同一个坐标可能不只有一家商店。

FJ 从坐标为 $0$ 的地方出发并且只能向前走，直到到达坐标为 $E$ 的地方，并且需要买到 $K$ 吨饲料。他可以在沿途任意一家商店停下来买饲料。

请你求出 FJ 购买并运输 $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$。