Treść zadania

Pasaż handlowy JOI prowadzi program kart punktowych. Każda karta punktowa ma $2N$ pól. Przy zakupie towaru można wziąć udział w losowaniu i w zależności od wyniku na polu przybijana jest pieczątka „wygrana” albo „pudło”. Na tym samym polu pieczątka nigdy nie jest przybijana $2$ razy. Kartę punktową, na której pieczątka wygranej znajduje się na co najmniej $N$ spośród $2N$ pól, można wymienić na nagrodę. Ponadto pieczątkę na karcie punktowej można zmienić na inną w cenie $1$ jena za $1$ pole.

JOI-kun ma $M$ kart punktowych, na których wszystkie $2N$ pól są zapełnione. Na karcie punktowej $i$ ($1 \le i \le M$) przybito $A_i$ pieczątek wygranej oraz $B_i$ pieczątek pudła. JOI-kun chciałby zdobyć co najmniej $M - 1$ nagród.

Oblicz minimalny koszt potrzebny, aby JOI-kun zdobył co najmniej $M - 1$ nagród.

Wejście

Wejście składa się z $M + 1$ wierszy.

W wierszu $1$ zapisane są oddzielone spacją $2$ liczby całkowite $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$). Oznacza to, że karta punktowa ma $2N$ pól, a JOI-kun posiada $M$ kart punktowych.

W $i$-tym wierszu ($1 \le i \le M$) spośród kolejnych $M$ wierszy zapisane są po $2$ liczby całkowite $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), oznaczające, że na karcie punktowej $i$ przybito $A_i$ pieczątek wygranej oraz $B_i$ pieczątek pudła.

Wyjście

Wypisz w $1$ wierszu minimalny koszt potrzebny, aby JOI-kun zdobył co najmniej $M - 1$ nagród.

Przykłady wejścia i wyjścia

Przykład wejścia 1

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

Przykład wyjścia 1

4

Przykład wejścia 2

5 4
5 5
8 2
3 7
8 2

Przykład wyjścia 2

0

W przykładzie wejścia 1, jeśli na karcie punktowej $1$ zamienimy $3$ pieczątki pudła na pieczątki wygranej, a na karcie punktowej $3$ zamienimy $1$ pieczątkę pudła na pieczątkę wygranej, to za $4$ jeny $4$ ($= 5 - 1$) karty będzie można wymienić na nagrody i jest to koszt minimalny.

W przykładzie wejścia 2 już $3$ ($= 4 - 1$) karty można wymienić na nagrody, więc nie trzeba niczego zmieniać.