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