問題

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 個以上の景品を得るために必要な費用の最小値を求めよ．

入力例 1

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

出力例 1

4

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

入力例 2

5 4
5 5
8 2
3 7
8 2

出力例 2

0

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