No.5 ポイントカード (Point Card)

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

JOI 商店街ではポイントカードのサービスを行っている．各ポイントカードには $2N$ 個のマスがある．商品を購入すると，くじを引くことができ，結果によって「当たり」か「はずれ」の印がマスに押される．同じマスに印が $2$ 回押されることはない．$2N$ 個のマスのうち $N$ 個以上のマスに当たりの印が書かれたポイントカードは，景品と交換することができる． また，ポイントカードの印は，$1$ マスにつき $1$ 円で書き換えてもらうことができる．

JOI 君は $2N$ 個のマスが全て埋まっているポイントカードを $M$ 枚持っている．ポイントカード $i (1 ≦ i ≦ M)$ には，$Ai$ 個の当たり印と，$Bi$ 個のはずれ印が押されている．JOI 君は $M - 1$ 個以上の景品が欲しい．

JOI 君が $M - 1$ 個以上の景品を得るために必要な費用の最小値を求めよ．

入力

入力は $M + 1$ 行からなる．

1 行目には，2 個の整数 $N, M (1 ≦ N ≦ 1000, 1 ≦ M ≦ 1000)$ が空白を区切りとして書かれている．これは，ポイントカードには $2N$ 個のマスがあり，JOI 君が $M$ 枚のポイントカードを持っていることを表す．

続く $M$ 行のうちの $i$ 行目 $(1 ≦ i ≦ M)$ には，それぞれ 2 個の整数 $Ai, Bi (0 ≦ Ai ≦ 2N, 0 ≦ Bi ≦ 2N, Ai + Bi = 2N)$ が書かれており，ポイントカード $i$ には $Ai$ 個の当たり印と $Bi$ 個のはずれ印が押されていることを表す．

出力

JOI 君が $M - 1$ 個以上の景品を得るために必要な費用の最小値を 1 行で出力せよ．

入出力例

4 5
1 7
6 2
3 5
4 4
0 8

4

入力例 1 においては，ポイントカード $1$ のはずれ印を $3$ つ当たり印に書き換えてもらい，ポイントカード $3$ のはずれ印を $1$ つ当たり印に書き換えてもらうと，$4$ 円で $4 (= 5 - 1)$ 枚のカードが景品と交換可能になり，これが最小の費用である．

5 4
5 5
8 2
3 7
8 2

 
0

入力例 2 においては，既に $3 (= 4 - 1)$ 枚のカードが景品と交換可能なので，書き換えてもらう必要ない．