ポイントカード (Point Card)
日本語
Language
Contribute a translation- Time limit
- 10000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
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\) 個以上の景品を得るために必要な費用の最小値を求めよ．
Input
入力は \(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\) 個のはずれ印が押されていることを表す．
Output
JOI 君が \(M - 1\) 個以上の景品を得るために必要な費用の最小値を \(1\) 行で出力せよ．
Examples
4 5 1 7 6 2 3 5 4 4 0 8
4
入力例 \(1\) においては，ポイントカード \(1\) のはずれ印を \(3\) つ当たり印に書き換えてもらい，ポイントカード \(3\) のはずれ印を \(1\) つ当たり印に書き換えてもらうと，\(4\) 円で \(4 \: (= 5 - 1)\) 枚のカードが景品と交換可能になり，これが最小の費用である．
5 4 5 5 8 2 3 7 8 2
0
入力例 \(2\) においては，既に \(3 \: (= 4 - 1)\) 枚のカードが景品と交換可能なので，書き換えてもらう必要ない．
Notes
JOI 2017 · JCIOI · CC BY-SA 4.0
Tags
No tags yet