Problem Description

JOI Shopping Street has a point card service. Each point card has $2N$ squares. When a product is purchased, a lottery can be drawn, and depending on the result, a "hit" or "miss" stamp is placed on a square. No square will receive a stamp more than once. A point card with $N$ or more "hit" stamps can be exchanged for a prize. Additionally, the stamps on the point card can be changed for $1$ yen per square.

JOI has $M$ point cards with all $2N$ squares filled. The $i$-th point card ($1 \leq i \leq M$) has $A_i$ "hit" stamps and $B_i$ "miss" stamps. JOI wants at least $M - 1$ prizes.

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

Input Format

The input consists of $M + 1$ lines.

The first line contains two integers $N, M$ ($1 \leq N \leq 1,000$, $1 \leq M \leq 1,000$), which indicate that each point card has $2N$ squares and JOI has $M$ point cards.

The next $M$ lines each contain two integers $A_i, B_i$ ($0 \leq A_i \leq 2N$, $0 \leq B_i \leq 2N$, $A_i + B_i = 2N$), which indicate that the $i$-th point card has $A_i$ "hit" stamps and $B_i$ "miss" stamps.

Output Format

Output the minimum cost required for JOI to get at least $M - 1$ prizes in one 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

Notes/Hints

Sample Explanation 1

In the first input example, changing $3$ "miss" stamps on the first point card and $1$ "miss" stamp on the third point card to "hit" stamps costs $4$ yen, making $4$ (=$5 - 1$) cards exchangeable for prizes, which is the minimum cost.

Sample Explanation 2

In the second input example, $3$ (=$4 - 1$) cards are already exchangeable for prizes, so no changes are needed.

见题面 Input 部分

见题面 Output 部分