C - 増築王高橋君 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は友人達ととあるゲームをしている。

このゲームでは、プレイヤーは建物を購入し、増改築し、できるだけ多くお金を稼ぐことが目的となる。

高橋君は現在 2 位であり、どうにかして首位の青木君より多くのお金を稼がなければならない。

高橋君は、最も多くの回数増築したものに与えられる称号「増築王」を手に入れることで、政府から受ける援助金を利用して勝利しようと計画した。長年の経験から、あと K 回増築することで増築王になれることが分かっている。

高橋君は現在 N 軒の建物を所有している。建物には 1 から N まで番号がついている。最初、どの建物も増築されていない。

建物 i (1 ≦ i ≦ N) について、以下のことが分かっている。

  • 建物 i の増築前の価格は A_i である。
  • 建物 i を 1 回増築するには、建物 i の現在の価格に等しい費用が必要となる。
  • 建物 i の価格は、1 回増築する度に D_i だけ上昇する。

高橋君は他の戦略も同時並行で実施するので、増築にかけるお金の合計値ができるだけ少なくなるようにしたい。

あなたは高橋君の代わりに K 回増築するのに必要な価格の合計値として考えられる最小値を求めてほしい。

入力

入力は以下の形式で標準入力から与えられる。

K
N
A_1 D_1
A_2 D_2
:
A_N D_N
  • 1 行目には、増築王になるために必要な増築の回数 K (1 ≦ K ≦ 10^8) が与えられる。
  • 2 行目には、高橋君が所有している建物の軒数 N (1 ≦ N ≦ 10^5) が与えられる。
  • 3 行目から N 行では、建物の情報が与えられる。このうち i 行目では整数 A_i (1 ≦ A_i ≦10^3) と整数 D_i (1 ≦ D_i ≦10^3) が空白を区切りとして与えられる。

部分点

この問題には部分点が設定されている。

  • K ≦ 300 かつ N ≦ 300 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • K ≦ 5,000 かつ N ≦ 5,000 を満たすデータセット 2 に正解した場合は、上記とは別に 10 点が与えられる。
  • K ≦ 10^5 を満たすデータセット 3 に正解した場合は、上記とは別に 15 点が与えられる。
  • 追加制約のないデータセット 4 に正解した場合は、上記とは別に 45 点が与えられる。

出力

K 回増築するのに必要な金額の合計として考えられるものの最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

4
3
10 3
12 4
15 5

出力例1

50

例えば、以下のように増築します。

  1. 建物 1 を増築します。現在の建物 1 の価格は 10 なので、増築にかかった金額の合計は 10 となります。また、増築後の建物 1 の価格は 13 になります。
  2. 建物 1 を増築します。現在の建物 1 の価格は 13 なので、増築にかかった金額の合計は 23 となります。また、増築後の建物 1 の価格は 16 になります。
  3. 建物 2 を増築します。現在の建物 2 の価格は 12 なので、増築にかかった金額の合計は 35 となります。また、増築後の建物 2 の価格は 16 になります。
  4. 建物 3 を増築します。現在の建物 3 の価格は 15 なので、増築にかかった金額の合計は 50 となります。また、増築後の建物 3 の価格は 20 になります。

このようにすることで、4 回増築するのにかかる金額を 50 にすることができます。

入力例2

8
4
1 1
10 1
100 1
1000 1

出力例2

36

建物 1 を 8 回増築します。