Farmer John 需要到鎮上買 $K$（$1 \le K \le 100$）磅飼料。卡車裝載 $K$ 磅飼料行駛 $D$ 英里的費用為 $D*K$ 美分。
縣裡的飼料市場有 $N$（$1 \le N \le 100$）家販售飼料的商店，編號為 $1..N$。它們位於 $X$ 軸上一段長 $E$（$1 \le E \le 350$）的線段上。商店 $i$ 的位置為 $X_{i}$（$0 < X_{i} < E$），最多可向 FJ 販售 $F_{i}$（$1 \le F_{i} \le 100$）磅，每磅價格 $C_{i}$（$1 \le C_{i} \le 1,000,000$）美分。同一個 $X$ 軸位置可能有多家商店。
FJ 從數軸位置 0 出發，只能向正方向行駛，最終帶著至少 $K$ 磅飼料到達位置 $E$。他可在途中的任何商店停下，購買不超過該店上限的任意數量。
購買並運輸 $K$ 磅飼料的最小費用是多少？FJ 知道有解。
例如，FJ 需要兩磅飼料，數軸範圍為 $0..5$，三家商店位於 1、3、4：
0 1 2 3 4 5
+---|---+---|---|---+
1 1 1 可購買的飼料磅數
1 2 2 每磅價格（美分）最佳是從第二家、第三家各買一磅，每磅兩美分，購買共花費 4。他從 3 到 4 行駛 1 單位長度，載有 1 磅，費用為 $1*1 = 1$ 美分。
他從 4 到 5 行駛 1 單位長度，載有 2 磅，費用為 $1*2 = 2$ 美分。
總費用為 $4+1+2 = 7$ 美分。
輸入格式
第 1 行：三個以空格分隔的整數 $K$、$E$ 和 $N$。
第 $2..N+1$ 行：第 $i+1$ 行包含三個以空格分隔的整數 $X_{i}$、$F_{i}$ 和 $C_{i}$。
輸出格式
- 第 1 行：一個整數，表示 FJ 購買並運輸飼料的最小費用。
範例
輸入格式 1
2 5 3 3 1 2 4 1 2 1 1 1
輸出格式 1
7
題目作者：Tom Conerly, 2009