레이팅 미적용설명
JOI 商店街ではポイントカードのサービスを行っている.各ポイントカードには 2N 個のマスがある.商品を購入すると,くじを引くことができ,結果によって「当たり」か「はずれ」の印がマスに押される.同じマスに印が 2 回押されることはない.2N 個のマスのうち N 個以上のマスに当たりの印が書かれたポイントカードは,景品と交換することができる.
また,ポイントカードの印は,1 マスにつき 1 円で書き換えてもらうことができる.
JOI 君は 2N 個のマスが全て埋まっているポイントカードを M 枚持っている.ポイントカード i (1 ≦ i ≦ M) には,A i 個の当たり印と,B i 個のはずれ印が押されている.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 個の整数 A i , B i (0 ≦ A i ≦ 2N, 0 ≦ B i ≦ 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출력
4문제 정보