시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 13 10 7 70.000%

문제

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

예제 입력 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) 枚のカードが景品と交換可能なので,書き換えてもらう必要ない.

※各入出力例のデータは,右クリック等によりファイルに保存して利用可能です.