Problem

JOI Shopping Street offers a point card service. Each point card has $2N$ squares. When you purchase an item, you can draw a lot, and depending on the result, a "win" or "miss" stamp is pressed onto a square. No square is stamped $2$ times. A point card that has win stamps written on at least $N$ squares out of the $2N$ squares can be exchanged for a prize. Also, a stamp on a point card can be rewritten for $1$ yen per $1$ square.

JOI-kun has $M$ point cards in which all $2N$ squares are filled. On point card $i$ ($1 \le i \le M$), there are $A_i$ win stamps and $B_i$ miss stamps pressed. JOI-kun wants at least $M - 1$ prizes.

Find the minimum cost required for JOI-kun to obtain at least $M - 1$ prizes.

Input

The input consists of $M + 1$ lines.

On line $1$, $2$ integers $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) are written separated by a space. This indicates that each point card has $2N$ squares and JOI-kun has $M$ point cards.

On line $i$ ($1 \le i \le M$) of the following $M$ lines, $2$ integers $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$) are written, indicating that point card $i$ has $A_i$ win stamps and $B_i$ miss stamps pressed on it.

Output

Print the minimum cost required for JOI-kun to obtain at least $M - 1$ prizes in $1$ line.

Sample Input and Output

Sample Input 1

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

Sample Output 1

4

Sample Input 2

5 4
5 5
8 2
3 7
8 2

Sample Output 2

0

In Sample Input 1, if JOI-kun has $3$ miss stamps on point card $1$ rewritten into win stamps and $1$ miss stamp on point card $3$ rewritten into a win stamp, then for $4$ yen, $4$ ($= 5 - 1$) cards can be exchanged for prizes, and this is the minimum cost.

In Sample Input 2, since $3$ ($= 4 - 1$) cards can already be exchanged for prizes, there is no need to have any stamps rewritten.