포인트 카드

JOI 상점가에서는 포인트 카드 서비스를 운영한다. 포인트 카드 한 장에는 도장을 찍는 칸이 $2N$개 있다. 상품을 구매하면 뽑기를 하고, 결과에 따라 빈 칸 하나에 '당첨' 도장 또는 '꽝' 도장이 찍힌다. 한 칸에 도장을 두 번 이상 찍을 수는 없다.

$2N$개 칸 중 $N$개 이상의 칸에 당첨 도장이 찍힌 포인트 카드는 경품 하나와 교환할 수 있다. 또한 이미 찍힌 도장 하나를 1엔을 내고 다른 종류의 도장으로 바꿀 수 있다.

JOI 군은 $2N$개 칸이 모두 채워진 포인트 카드를 $M$장 가지고 있다. $i$번째 포인트 카드에는 당첨 도장이 $A_i$개, 꽝 도장이 $B_i$개 찍혀 있다.

JOI 군은 경품을 $M-1$개 이상 얻으려고 한다. 이를 위해 필요한 비용의 최솟값을 구하라.

입력은 $M+1$개 줄로 이루어진다.

첫째 줄에 두 정수 $N$, $M$ ($1 \le N \le 1000$, $1 \le M \le 1000$)이 공백으로 구분되어 주어진다. 포인트 카드 한 장에 칸이 $2N$개 있고, JOI 군이 포인트 카드를 $M$장 가지고 있다는 뜻이다.

다음 $M$개 줄 중 $i$번째 줄 ($1 \le i \le M$)에는 두 정수 $A_i$, $B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$)가 주어진다. 포인트 카드 $i$에 당첨 도장이 $A_i$개, 꽝 도장이 $B_i$개 찍혀 있다는 뜻이다.

JOI 군이 경품을 $M-1$개 이상 얻는 데 필요한 비용의 최솟값을 엔 단위의 정수로 한 줄에 출력한다.

예제 1에서는 포인트 카드 1의 꽝 도장 3개와 포인트 카드 3의 꽝 도장 1개를 당첨 도장으로 바꾸면 4엔으로 $5-1=4$장의 카드를 경품과 교환할 수 있다. 이것이 최소 비용이다.

예제 2에서는 이미 $4-1=3$장의 카드를 경품과 교환할 수 있으므로 도장을 바꿀 필요가 없다.