JOI 2017 예선 2- 경품 > 문제은행 : 정보올림피아드&알고리즘




3029 : 경품

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
29 회   
시도횟수
68 회   

문제

지홍이는 M장의 상품권을 갖고 있다. 이 상품권은 동전으로 긁을 수 있는 은박지가 있는데, 새로 산 상품권은 은박지가 총 2×N개 있다. 지홍이는 이미 동전을 이용하여 몇 칸의 은박지를 긁었다.

 

이 상품권은 KOI 백화점에 있는 고객센터에서 경품으로 교환할 수 있는데, 상품권을 경품으로 교환하려면 N칸 이상의 은박지를 긁어야 한다.

 

지홍이는 M-1개의 경품을 갖고 싶기 때문에, 자신이 갖고 있는 상품권에서 은박지 몇 칸을 더 긁으려고 한다. 지홍이를 도와 최소 몇 칸의 은박지를 동전으로 긁어야 M-1개의 경품을 얻을 수 있는지 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 N, M이 주어진다. (1 ≦ N ≦ 1,000, 1 ≦ M ≦ 1,000) 두 번째 줄부터 M개의 줄에는 각 상품권에서 긁은 은박지 영역의 수 A[i]와 안 긁은 칸의 수 B[i]가 주어진다. (0 ≦ A[i] ≦ 2N, 0 ≦ B[i] ≦ 2N, A[i] + B[i] = 2N)

출력형식

지홍이가 M-1개의 경품을 갖기 위해 더 긁어야 하는 칸의 최솟값을 출력한다.

입력 예

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

출력 예

4

입력 예

5 4
5 5
8 2
3 7
8 2

출력 예

0

Hint!

예제 1 설명 지홍이가 첫 번째 상품권에서 세 칸을, 세 번째 상품권에서 한 칸을 긁으면 1~4번째 상품권으로 경품을 얻을 수 있다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP