문제
JOI 상점가에서는 포인트 카드 서비스를 한다. 각 포인트 카드에는 칸이 \(2N\)개 있다. 물건을 사면 제비를 뽑아, 결과에 따라 칸에 「당첨」 또는 「꽝」 도장을 찍는다. 같은 칸에 도장을 두 번 찍지는 않는다. \(2N\)개 칸 가운데 \(N\)개 이상에 당첨 도장이 찍힌 포인트 카드는 경품과 바꿀 수 있다. 또 포인트 카드의 도장은 칸 하나당 \(1\)원에 바꿔 찍을 수 있다. JOI 군은 \(2N\)개 칸이 모두 채워진 포인트 카드를 \(M\)장 가지고 있다. 포인트 카드 \(i\) (\(1 \le i \le M\))에는 당첨 도장이 \(A_i\)개, 꽝 도장이 \(B_i\)개 찍혀 있다. JOI 군은 경품을 \(M-1\)개 이상 갖고 싶다. JOI 군이 경품을 \(M-1\)개 이상 얻기 위해 필요한 비용의 최솟값을 구하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\) \(M\)
\(A_1\) \(B_1\)
\(\vdots\)
\(A_M\) \(B_M\)
- 입력은 \(M+1\)줄이다.
- 첫째 줄에 정수 \(N\), \(M\)이 공백 하나로 구분되어 주어진다. 포인트 카드에 칸이 \(2N\)개 있고, JOI 군이 포인트 카드를 \(M\)장 가지고 있음을 나타낸다.
- 이어지는 \(M\)줄 중 \(i\)번째 줄(\(1 \le i \le M\))에 정수 \(A_i\), \(B_i\)가 공백 하나로 구분되어 주어지고, 포인트 카드 \(i\)에 당첨 도장이 \(A_i\)개, 꽝 도장이 \(B_i\)개 찍혀 있음을 나타낸다.
- \(1 \le N \le 1000\)
- \(1 \le M \le 1000\)
- \(0 \le A_i \le 2N\)
- \(0 \le B_i \le 2N\)
- \(A_i + B_i = 2N\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에, JOI 군이 경품을 \(M-1\)개 이상 얻기 위해 필요한 비용의 최솟값을 출력한다.
예시 1
입력
4 5
1 7
6 2
3 5
4 4
0 8
출력
4
설명
포인트 카드 \(1\)의 꽝 도장 \(3\)개를 당첨으로 바꾸고, 포인트 카드 \(3\)의 꽝 도장 \(1\)개를 당첨으로 바꾸면 \(4\)원으로 \(4\)장(\(5-1\)장)을 경품과 바꿀 수 있다. 이것이 최소 비용이다.
예시 2
입력
5 4
5 5
8 2
3 7
8 2
출력
0
설명
이미 \(3\)장(\(4-1\)장)을 경품과 바꿀 수 있으므로 도장을 바꿀 필요가 없다.