Tehtävä

JOI-kauppakadulla on käytössä pistekorttipalvelu. Jokaisessa pistekortissa on $2N$ ruutua. Kun ostaa tuotteen, saa nostaa arvan, ja tuloksen mukaan ruutuun leimataan ”voitto” tai ”huti”. Samaan ruutuun ei koskaan leimata $2$ kertaa. Pistekortin, jonka $2N$ ruudusta vähintään $N$ ruudussa on voittoleima, voi vaihtaa palkintoon. Lisäksi pistekortin leiman voi pyytää muuttamaan hintaan $1$ jeni per $1$ ruutu.

JOI-kunilla on $M$ pistekorttia, joiden kaikki $2N$ ruutua ovat täynnä. Pistekortissa $i$ ($1 \le i \le M$) on $A_i$ voittoleimaa ja $B_i$ hutileimaa. JOI-kun haluaa vähintään $M - 1$ palkintoa.

Etsi pienin kustannus, jolla JOI-kun voi saada vähintään $M - 1$ palkintoa.

Syöte

Syöte koostuu $M + 1$ rivistä.

Rivillä $1$ on $2$ välilyönnillä erotettua kokonaislukua $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$). Tämä tarkoittaa, että pistekortissa on $2N$ ruutua ja JOI-kunilla on $M$ pistekorttia.

Seuraavien $M$ rivin rivillä $i$ ($1 \le i \le M$) on $2$ kokonaislukua $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), mikä tarkoittaa, että pistekortissa $i$ on $A_i$ voittoleimaa ja $B_i$ hutileimaa.

Tuloste

Tulosta $1$ riville pienin kustannus, joka tarvitaan, jotta JOI-kun saa vähintään $M - 1$ palkintoa.

Syöte- ja tulosteesimerkit

Syöteesimerkki 1

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

Tulosteesimerkki 1

4

Syöteesimerkki 2

5 4
5 5
8 2
3 7
8 2

Tulosteesimerkki 2

0

Syöteesimerkissä 1, jos pistekortista $1$ muutetaan $3$ hutileimaa voittoleimoiksi ja pistekortista $3$ muutetaan $1$ hutileima voittoleimaksi, niin $4$ jenillä saadaan $4$ ($= 5 - 1$) korttia vaihdettaviksi palkintoihin, ja tämä on pienin kustannus.

Syöteesimerkissä 2 jo valmiiksi $3$ ($= 4 - 1$) korttia voidaan vaihtaa palkintoihin, joten leimoja ei tarvitse muuttaa.