問題

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

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

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

入力

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

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

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

出力

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

入出力例

入力例 1

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

出力例 1

4

入力例 2

5 4
5 5
8 2
3 7
8 2

出力例 2

0

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

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