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 から正方向だけ進み、$E$ に少なくとも $K$ ポンドで到着します。途中任意の店で上限まで好きな量を買えます。

$K$ の購入輸送最小費用を求めます。十分買える保証があります。

二ポンド必要、数直線 $0..5$ の 1、3、4 に三店の例：

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      購入可能ポンド
          1       2   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