AT_joi2017yo_b ポイントカード (Point Card)

[problemUrl]: https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b JOI 商店街ではポイントカードのサービスを行っている．各ポイントカードには $ 2N $ 個のマスがある．商品を購入すると，くじを引くことができ，結果によって「当たり」か「はずれ」の印がマスに押される．同じマスに印が $ 2 $ 回押されることはない．$ 2N $ 個のマスのうち $ N $ 個以上のマスに当たりの印が書かれたポイントカードは，景品と交換することができる．また，ポイントカードの印は，$ 1 $ マスにつき $ 1 $ 円で書き換えてもらうことができる． JOI 君は $ 2N $ 個のマスが全て埋まっているポイントカードを $ M $ 枚持っている．ポイントカード $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) には，$ A_i $ 個の当たり印と，$ B_i $ 個のはずれ印が押されている．JOI 君は $ M\ -\ 1 $ 個以上の景品が欲しい． JOI 君が $ M\ -\ 1 $ 個以上の景品を得るために必要な費用の最小値を求めよ． - - - - - -

入力は $ M\ +\ 1 $ 行からなる． $ 1 $ 行目には，$ 2 $ 個の整数 $ N,\ M $ ($ 1\ \leqq\ N\ \leqq\ 1\,000 $，$ 1\ \leqq\ M\ \leqq\ 1\,000 $) が空白を区切りとして書かれている．これは，ポイントカードには $ 2N $ 個のマスがあり，JOI 君が $ M $ 枚のポイントカードを持っていることを表す． 続く $ M $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ M $) には，それぞれ $ 2 $ 個の整数 $ A_i,\ B_i $ ($ 0\ \leqq\ A_i\ \leqq\ 2N $，$ 0\ \leqq\ B_i\ \leqq\ 2N $，$ A_i\ +\ B_i\ =\ 2N $) が書かれており，ポイントカード $ i $ には $ A_i $ 個の当たり印と $ B_i $ 個のはずれ印が押されていることを表す．

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

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