페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8712

포인트 카드 1s 512MB

문제

JOI 상점가에서는 포인트 카드 서비스를 실시하고 있다.

각 포인트 카드에는 도장을 찍을 수 있는 칸이 총 2N개 있어, 상품을 구매하면 뽑기를 해서 결과에 따라 '당첨' 또는 '꽝' 도장이 찍힌다.

한 칸에 두 번 이상 도장을 찍을 수는 없다.

2N개 중 N개 이상의 칸에 당첨 도장이 찍힌 포인트 카드는 경품과 교환할 수 있다.

또, 한 칸에 찍힌 도장을 1엔을 내고 다른 도장으로 바꿀 수 있다.

JOI 군은 2N개 칸을 다 채운 포인트 카드를 M장 가지고 있다.

i번째 포인트 카드에는 A_i개의 당첨 도장과, B_i개의 꽝 도장이 찍혀 있다.

JOI 군은 M-1개 이상의 경품을 가지려고 한다. 이에 필요한 비용의 최솟값을 구하라.


입력

입력은 M+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

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

포인트 카드 1의 꽝 도장 3개와 포인트 카드 3의 꽝 도장 1개를 당첨 도장으로 바꾸면, 4엔으로 5-1=4장의 카드가 경품과 교환 가능하게 되어, 이것이 최소 비용이다.


예제 #2

5 4
5 5
8 2
3 7
8 2
0

이미 4-1=3장의 카드가 경품과 교환 가능하므로 도장을 바꿀 필요가 없다.



출처

JOI 2016/2017 예선 2번
로그인해야 코드를 작성할 수 있어요.