Farmer John 要到镇上买 $K$（$1 \le K \le 10,000$）磅饲料。带 $K$ 磅开一英里花 $K*K$ 美分，开 $D$ 英里花 $D*K*K$ 美分。
可在 $N$（$1 \le N \le 500$）家编号 $1..N$ 的店买。店在 $X$ 轴长 $E$（$1 \le E \le 500$）英里的线段上。店 $i$ 位于 $X_{i}$（$0 < X_{i} < E$），最多卖 $F_{i}$（$1 \le F_{i} \le 10,000$）磅，每磅 $C_{i}$（$1 \le C_{i} \le 10,000,000$）美分。同一点可能多店。
从 0 出发只能正向开，最终带至少 $K$ 磅到 $E$。沿路可停任何店，买不超过该店上限的任意量。
求购买运输 $K$ 磅的最小花费，保证能买够。
例如需要两磅，店在数轴 $0..5$ 的 1、3、4：
0 1 2 3 4 5 X
+---|---+---|---|---+
1 1 1 可买磅数
1 2 2 每磅美分第二第三店各买一磅最便宜，每磅两美分，购买共 4。0 到 3 无货，开车免费。3 到 4 一英里带一磅，花 $1*1*1 = 1$ 美分。
4 到 5 一英里带两磅，花 $1*2*2 = 4$ 美分。
购买 $2+2$、运费 $1+4$，总 $2 + 2 + 1 + 4 = 9$ 美分。
输入格式
- 第 1 行：空格分隔整数 $K$、$E$、$N$。
- 第 $2..N+1$ 行：第 $i+1$ 行为空格分隔整数 $X_{i}$、$F_{i}$、$C_{i}$。
输出格式
- 第 1 行：一个整数，购买运输饲料最小花费。
样例
输入格式 1
2 5 3 3 1 2 4 1 2 1 1 1
输出格式 1
9
题目作者：Tom Conerly，2009