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$）、販売上限は $F_{i}$ ポンド（$1 \le F_{i} \le 100$）、単価は $C_{i}$ セント（$1 \le C_{i} \le 1,000,000$）です。同じ $X$ 軸の点に複数の店があることもあります。

FJ は数直線の 0 から正方向だけに走り、最後に少なくとも $K$ ポンドを持って $E$ に着きます。途中のどの店でも止まり、その店の上限まで任意量を購入できます。

$K$ ポンドの購入と輸送に必要な最小費用はいくらでしょうか。解の存在は保証されています。

例えば $0..5$ の数直線で、位置 1、3、4 の 3 店から 2 ポンドを買う場合：

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      販売可能な飼料（ポンド）
          1       2   2      1 ポンド当たりのセント

2 番目と 3 番目の店で各 1 ポンド買うのが最良です。各 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 行目：飼料の購入と輸送の最小費用を表す整数。

入出力例

入力 1

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

出力 1

7

問題作成者：Tom Conerly, 2009