AT_abc153_e [ABC153E] Crested Ibis vs Monster

[problemUrl]: https://atcoder.jp/contests/abc153/tasks/abc153_e トキはモンスターと戦っています。 モンスターの体力は $ H $ です。 トキは $ N $ 種類の魔法が使え、$ i $ 番目の魔法を使うと、モンスターの体力を $ A_i $ 減らすことができますが、トキの魔力を $ B_i $ 消耗します。 同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。 モンスターの体力を $ 0 $ 以下にすればトキの勝ちです。 トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ N $ $ A_1 $ $ B_1 $ $ : $ $ A_N $ $ B_N $

トキがモンスターに勝つまでに消耗する魔力の最小値を出力せよ。

### 制約 - $ 1\ \leq\ H\ \leq\ 10^4 $ - $ 1\ \leq\ N\ \leq\ 10^3 $ - $ 1\ \leq\ A_i\ \leq\ 10^4 $ - $ 1\ \leq\ B_i\ \leq\ 10^4 $ - 入力中のすべての値は整数である。 ### Sample Explanation 1 最初に $ 1 $ 番目の魔法を使い、トキの魔力を $ 3 $ 消耗して、モンスターの体力を $ 8 $ 減らします。モンスターの体力は $ 1 $ になります。 次に $ 3 $ 番目の魔法を使い、トキの魔力を $ 1 $ 消耗して、モンスターの体力を $ 2 $ 減らします。モンスターの体力は $ -1 $ になります。 これにより、トキが消耗した魔力の合計は $ 4 $ になります。 ### Sample Explanation 2 $ 1 $ 番目の魔法を $ 100 $ 回使うのが最適です。