题目描述

同学们组团去图书馆学习，但他们不想起身拿书。小杨自告奋勇，表示自己可以给他们带回一些书。同学们一共需要 $k$ 本书。

现在他在图书馆最深处的书架（位置 $0$），图书馆门口的座位在位置 $e$。从位置 $0$ 到位置 $e$ 这一路上共有 $n$ 个书架，每个书架的位置为 $x_i$（$0 \le x_i \le e$，位置值越大越靠近门口），有 $f_i$ 本书可供借用。

搬书和取书都是需要消耗体力的。取书时，小杨需要消耗 $c_i$ 的体力把 $1$ 本书从书架中抽出来；他手上每拿着 $1$ 本书走 $1$ 单位距离，就会消耗 $1$ 点体力值。

求小杨拿齐 $k$ 本书到达座位的最小体力消耗。保证小杨总能达成结果。

输入格式

第一行：$3$ 个整数 $k$、$e$、$n$。

接下来 $n$ 行：每行 $3$ 个整数 $x_i$、$f_i$、$c_i$。

输出格式

一个整数，表示答案。

样例

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

7

1 100 2
0 1 1
50 1 1

51

样例解释

样例 1 中，在位置 $3$ 消耗 $2$ 体力拿 $1$ 本书，消耗 $1$ 体力拿着书走到位置 $4$，消耗 $2$ 体力再拿一本书，消耗 $2$ 体力拿着这两本书走到位置 $5$，总消耗为 $7$。

样例 2 中，只需拿 $1$ 本书。书架 $1$（位置 $0$）取书消耗 $1$、搬运到座位（位置 $100$）消耗 $100$，共 $101$；书架 $2$（位置 $50$）取书消耗 $1$、搬运消耗 $50$，共 $51$。选择书架 $2$，总消耗为 $51$。

数据范围与约定

对于 $100\%$ 的数据，$1 \leq k \leq 100$，$1 \leq e \leq 350$，$1 \leq n \leq 100$，$1 \leq f_i \leq 10^9$，$1 \le c_i \leq 10^6$，且所有书架上的书总数不少于 $k$。位置 $x_i$ 满足 $0 \leq x_i \leq e$，且可能有多个书架位于同一位置。