问题 D：采购粮食

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

市场是一条笔直的直线，从位置 $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$, 含义如题所述。

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

$1\le S,M\le 100, 1\le N\le 350$;

$0 < x_i < N, 1\le c_i\le 100, 1\le p_i\le 10^6$

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

7