문제

JOI 상점가에서는 포인트 카드 서비스를 운영하고 있다. 각 포인트 카드에는 $2N$개의 칸이 있다. 상품을 구매하면 제비를 뽑을 수 있으며, 결과에 따라 '당첨' 또는 '꽝' 도장이 칸에 찍힌다. 같은 칸에 도장이 $2$번 찍히는 일은 없다. $2N$개의 칸 중 $N$개 이상의 칸에 당첨 도장이 찍힌 포인트 카드는 경품으로 교환할 수 있다. 또한, 포인트 카드의 도장은 $1$칸당 $1$엔으로 고쳐 쓸 수 있다.

JOI 군은 $2N$개의 칸이 모두 채워진 포인트 카드를 $M$장 가지고 있다. 포인트 카드 $i$ ($1 \le i \le M$)에는 $A_i$개의 당첨 도장과 $B_i$개의 꽝 도장이 찍혀 있다. JOI 군은 $M - 1$개 이상의 경품을 원한다.

JOI 군이 $M - 1$개 이상의 경품을 얻기 위해 필요한 비용의 최솟값을 구하여라.

입력

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

$1$번째 줄에는 $2$개의 정수 $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$)이 공백으로 구분되어 적혀 있다. 이는 포인트 카드에 $2N$개의 칸이 있으며, JOI 군이 $M$장의 포인트 카드를 가지고 있음을 나타낸다.

이어지는 $M$줄 중 $i$번째 줄 ($1 \le i \le M$)에는 각각 $2$개의 정수 $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

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

출력 예 1

4

입력 예 2

5 4
5 5
8 2
3 7
8 2

출력 예 2

0

입력 예 1에서는 포인트 카드 $1$의 꽝 도장 $3$개를 당첨 도장으로 고쳐 쓰고, 포인트 카드 $3$의 꽝 도장 $1$개를 당첨 도장으로 고쳐 쓰면, $4$엔으로 $4$ ($= 5 - 1$)장의 카드를 경품으로 교환할 수 있게 되며, 이것이 최소 비용이다.

입력 예 2에서는 이미 $3$ ($= 4 - 1$)장의 카드를 경품으로 교환할 수 있으므로 고쳐 쓸 필요가 없다.