Informatica Online Judge

  Point Card [1831 / 0727]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 50   Total Tried : 51


The Champion of this Problem (C++) : gs16109 - 0ms / 111byte
My Best Submission (C++) : N/A

[JOI 16/17 예선]

Background

GS상점가에는 포인트카드 서비스가 있다

각 포인트카드에는 $2n$개의 칸이 있다.

상품을 구입하면 "당첨"과 "꽝"이 나올 수 있는 뽑기를 하게 되며 그 결과를 도장으로 각 칸에 찍는다.

같은 칸에 2개의 도장을 찍는 경우는 없다.

$2n$개의 칸 중 $n$개 이상의 칸이 "당첨"으로 된 포인트카드는 경품과 교환할 수 있다.

또 포인트카드의 도장의 내용을 1개 바꾸는데 1원의 비용이 든다.

경곽이는 $2n$개의 칸을 모두 채운 포인트카드를 $m$개를 가지고 있다.

포인트카드 $i$에는 $a_i$개의 "당첨" 도장이 찍혀있고, $b_i$개의 "꽝" 도장이 찍혀있다.

경곽이는 $m-1$개 이상의 경품을 가지고 싶어한다.

경곽이가 $m-1$개 이상의 경품을 가지기 위해서 필요한 비용의 최소값을 구하시오.

Input

첫 번째 줄에는 2개의 정수 $n$, $m$이 공백으로 구분되어 입력된다.

두 번째 줄부터 m줄에 걸쳐서 $a_i$, $b_i$가 입력된다.

[입력값의 정의역]

$1 ≦ N ≦ 1000, 1 ≦ M ≦ 1000, 1 ≦ i ≦ M$

Output

경곽이가 $m-1$개 이상의 경품을 얻기위해서 필요한 최소비용을 출력한다.

IO Example

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

출력
4


입력2
5 4
5 5
8 2
3 7
8 2

출력2
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]