Point Card

Time limit2sMemory limit512 MB

Summary

Given M cards with A wins out of 2N cells, pay 1 yen per flipped stamp to make at least M-1 cards hold N or more wins; minimize total cost.

Level: Medium4 of 10
Topics: Greedy, Sorting, Array
Solved: No attempts yet

Problem

The JOI shopping district runs a point card service. Each point card has $2N$ cells for stamps. Every time you buy something, you draw a lottery, and one empty cell receives either a "win" stamp or a "miss" stamp depending on the result. A cell can never be stamped more than once.

A point card on which at least $N$ of the $2N$ cells carry a win stamp can be exchanged for one prize. You can also pay 1 yen to change any single stamp on a card into the other kind of stamp.

JOI has $M$ point cards, and all $2N$ cells of each card are filled. Card $i$ has $A_i$ win stamps and $B_i$ miss stamps.

JOI wants to get at least $M-1$ prizes. Find the minimum cost needed to do this.

Input

The input consists of $M+1$ lines.

The first line contains two integers $N$ and $M$ ( $1 \le N \le 1000$ , $1 \le M \le 1000$ ) separated by a space. Each point card has $2N$ cells, and JOI has $M$ point cards.

The $i$ -th of the next $M$ lines ( $1 \le i \le M$ ) contains two integers $A_i$ and $B_i$ ( $0 \le A_i \le 2N$ , $0 \le B_i \le 2N$ , $A_i + B_i = 2N$ ). Point card $i$ has $A_i$ win stamps and $B_i$ miss stamps.

Output

Print on one line the minimum cost, in yen, that JOI needs to get at least $M-1$ prizes.

Hint

In Example 1, changing 3 miss stamps on card 1 and 1 miss stamp on card 3 into win stamps costs 4 yen and makes $5-1=4$ cards exchangeable for prizes. This is the minimum cost.

In Example 2, $4-1=3$ cards can already be exchanged for prizes, so no stamp needs to change.

Examples2

Example 1
Input
```
4 5
1 7
6 2
3 5
4 4
0 8
```
Expected output
```
4
```
Example 2
Input
```
5 4
5 5
8 2
3 7
8 2
```
Expected output
```
0
```