当前没有测试数据。

粮食采购

题目描述

食堂的张师傅，开车来到市场采购粮食。

市场是一条笔直的直线，从位置 $0$ 开始 到位置 $N$ 结束，每个整点上都开设了一个商店。

这些商店中，只有 $M$ 个商店是粮食店，供应张师傅需要采购的粮食，这 $M$ 个商店中第 $i$ 个商店的位置为 $x_{i}$，粮食单价为 $p_{i}$ 元每公斤，有 $c_{i}$ 公斤的粮食供应给客人购买。

张师傅的车如果装了 $T$ 公斤的粮食，每行驶一个单位的距离，就要消耗 $T$ 元的油费，如果没有装粮食，油费忽略不计。

张师傅一共要采购 $S$ 公斤的粮食，请问他从位置 $0$ 开始，如果中途可以在任意的粮食店采购粮食，但不能回头，并一定要行驶到位置 $N$ 处，那么他最少要花费多少元？

输入

第 $1$ 行读入整数 $S,N,M$。

接下来 $M$ 行，每行读入 $3$ 个整数 $x_{i},c_{i},p_{i}$，含义如题所述。

请注意：本题在同一个位置，可能会有多家粮食店。

输出

输出一个整数，代表张师傅的最少花费。

样例

输入复制

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

输出复制

7

说明

样例 $1$ 解释

张师傅要采购 $2$ 公斤的粮食，整条街从位置 $0∼5$ 开设有商店，有 $3$ 个位置上开设有粮食店。

在位置 $3$ 的粮食店购买 $1$ 公斤的粮食，运输到位置 $5$ ，采购费用：$2$ 元，运输费用 $2$ 元。

在位置 $4$ 的粮食店购买 $1$ 公斤的粮食，运输到位置 $5$ ，采购费用：$2$ 元，运输费用 $1$ 元。

共计花费 $=2+2+2+1=7$ 元。

数据范围

对于 $100$% 的数据，$1≤S≤100$，$1≤N≤350$，$1≤M≤100$。

对于 $100$% 的数据，$0<x_{i}<N$，$1≤c_{i}≤100$，$1≤p_{i}≤10^{6}$。

数据保证所有粮食店的粮食供应量的总和能够满足张师傅的采购要求。