题目描述

小泽从坐标 $0$ 沿数轴前往坐标 $E$，要带回恰好 $K$ 吨物资。第 $i$ 家店位于 $X_i$，库存 $F_i$ 吨，单价 $C_i$。车辆装有 $q$ 吨物资行驶一单位距离会花费 $q$ 元，且只能向坐标增大的方向行驶。求购买与运输的最小总费用。

输入格式

第一行 $K,E,N$。接下来 $N$ 行为 $X_i,F_i,C_i$。

输出格式

输出最小总费用。

输入

40 154 1
44 78 320818

输出

12837120

输入

35 244 6
141 2 506313
55 57 788753
64 73 148625
50 66 734955
37 14 712927
193 60 604652

输出

5208175

输入

28 70 9
60 68 175990
61 39 353227
20 75 290732
57 55 777519
3 72 309894
2 55 817545
8 4 149823
21 53 396745
12 38 926503

输出

4823540

数据范围

$1\le K,N\le100$，$1\le E\le350$，$0<X_i<E$，$1\le F_i\le100$，$1\le C_i\le10^6$，总库存不少于 $K$。