Verkefni

Í JOI-verslunargötunni er boðið upp á punktkortaþjónustu. Á hverju punktkorti eru $2N$ reitir. Þegar vara er keypt má draga í happdrætti og eftir niðurstöðunni er stimplað „vinningur“ eða „núll“ í reit. Aldrei er stimplað $2$ sinnum í sama reitinn. Punktkorti sem hefur vinningsstimpil í að minnsta kosti $N$ reitum af $2N$ má skipta fyrir verðlaun. Einnig er hægt að láta breyta stimpli á punktkorti fyrir $1$ jen á hvern $1$ reit.

JOI-kun á $M$ punktkort þar sem allir $2N$ reitirnir eru fylltir. Á punktkorti $i$ ($1 \le i \le M$) eru $A_i$ vinningsstimplar og $B_i$ núllstimplar. JOI-kun vill fá að minnsta kosti $M - 1$ verðlaun.

Finndu lágmarkskostnaðinn sem þarf til að JOI-kun fái að minnsta kosti $M - 1$ verðlaun.

Inntak

Inntakið samanstendur af $M + 1$ línum.

Í línu $1$ standa $2$ heiltölur $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) aðskildar með bili. Þetta táknar að á punktkorti eru $2N$ reitir og að JOI-kun á $M$ punktkort.

Í línu $i$ ($1 \le i \le M$) af næstu $M$ línum standa $2$ heiltölur $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), sem táknar að á punktkorti $i$ eru $A_i$ vinningsstimplar og $B_i$ núllstimplar.

Úttak

Prentaðu í $1$ línu lágmarkskostnaðinn sem þarf til að JOI-kun fái að minnsta kosti $M - 1$ verðlaun.

Dæmi um inntak og úttak

Inntaksdæmi 1

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

Úttaksdæmi 1

4

Inntaksdæmi 2

5 4
5 5
8 2
3 7
8 2

Úttaksdæmi 2

0

Í inntaksdæmi 1, ef JOI-kun lætur breyta $3$ núllstimplum á punktkorti $1$ í vinningsstimpla og $1$ núllstimpli á punktkorti $3$ í vinningsstimpil, þá er hægt fyrir $4$ jen að skipta $4$ ($= 5 - 1$) kortum fyrir verðlaun, og þetta er lágmarkskostnaðurinn.

Í inntaksdæmi 2 er þegar hægt að skipta $3$ ($= 4 - 1$) kortum fyrir verðlaun, svo ekki er þörf á að breyta neinum stimplum.