Problem

Handlegaten JOI tilbyr en tjeneste med poengkort. Hvert poengkort har $2N$ ruter. Når man kjøper en vare, kan man trekke et lodd, og avhengig av resultatet blir det satt et stempel for «gevinst» eller «bom» i en rute. Det blir aldri satt stempel i samme rute $2$ ganger. Et poengkort som har gevinststempel i minst $N$ av de $2N$ rutene, kan byttes inn i en premie. I tillegg kan man få skrevet om et stempel på poengkortet for $1$ yen per $1$ rute.

JOI-kun har $M$ poengkort der alle de $2N$ rutene er fylt ut. På poengkort $i$ ($1 \le i \le M$) er det satt $A_i$ gevinststempler og $B_i$ bomstempler. JOI-kun ønsker seg minst $M - 1$ premier.

Finn den minste kostnaden som kreves for at JOI-kun skal få minst $M - 1$ premier.

Inndata

Inndata består av $M + 1$ linjer.

På linje $1$ står det $2$ heltall $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) atskilt med mellomrom. Dette betyr at hvert poengkort har $2N$ ruter, og at JOI-kun har $M$ poengkort.

På linje $i$ ($1 \le i \le M$) av de neste $M$ linjene står det $2$ heltall $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), som betyr at poengkort $i$ har $A_i$ gevinststempler og $B_i$ bomstempler.

Utdata

Skriv ut på $1$ linje den minste kostnaden som kreves for at JOI-kun skal få minst $M - 1$ premier.

Eksempler på inndata og utdata

Inndataeksempel 1

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

Utdataeksempel 1

4

Inndataeksempel 2

5 4
5 5
8 2
3 7
8 2

Utdataeksempel 2

0

I inndataeksempel 1 kan JOI-kun få skrevet om $3$ bomstempler på poengkort $1$ til gevinststempler og $1$ bomstempel på poengkort $3$ til gevinststempel; da kan $4$ ($= 5 - 1$) kort byttes i premier for $4$ yen, og dette er den minste kostnaden.

I inndataeksempel 2 kan allerede $3$ ($= 4 - 1$) kort byttes i premier, så det er ikke nødvendig å skrive om noen stempler.