Problem

JOI-shoppinggatan erbjuder en tjänst med poängkort. Varje poängkort har $2N$ rutor. När man köper en vara får man dra en lott, och beroende på resultatet stämplas antingen ”vinst” eller ”nit” i en ruta. Samma ruta stämplas aldrig $2$ gånger. Ett poängkort som har vinststämplar i minst $N$ av de $2N$ rutorna kan bytas mot ett pris. Dessutom kan man få en stämpel på ett poängkort ändrad för $1$ yen per $1$ ruta.

JOI-kun har $M$ poängkort där alla $2N$ rutor är ifyllda. På poängkort $i$ ($1 \le i \le M$) finns det $A_i$ vinststämplar och $B_i$ nitstämplar. JOI-kun vill ha minst $M - 1$ priser.

Beräkna den minsta kostnaden som krävs för att JOI-kun ska få minst $M - 1$ priser.

Indata

Indata består av $M + 1$ rader.

På rad $1$ står $2$ heltal $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) åtskilda av ett blanksteg. Detta anger att varje poängkort har $2N$ rutor och att JOI-kun har $M$ poängkort.

På rad $i$ ($1 \le i \le M$) av de följande $M$ raderna står $2$ heltal $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), vilket anger att poängkort $i$ har $A_i$ vinststämplar och $B_i$ nitstämplar.

Utdata

Skriv ut den minsta kostnaden som krävs för att JOI-kun ska få minst $M - 1$ priser på $1$ rad.

Exempel på indata och utdata

Indataexempel 1

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

Utdataexempel 1

4

Indataexempel 2

5 4
5 5
8 2
3 7
8 2

Utdataexempel 2

0

I indataexempel 1 kan JOI-kun låta ändra $3$ nitstämplar på poängkort $1$ till vinststämplar och $1$ nitstämpel på poängkort $3$ till en vinststämpel; då kan $4$ ($= 5 - 1$) kort bytas mot priser för $4$ yen, och detta är den minsta kostnaden.

I indataexempel 2 kan redan $3$ ($= 4 - 1$) kort bytas mot priser, så inga stämplar behöver ändras.