Deskripsi Masalah
Distrik Perbelanjaan JOI menyediakan layanan kartu poin. Setiap kartu poin memiliki $2N$ kotak. Ketika membeli barang, pelanggan dapat menarik undian, dan bergantung pada hasilnya, cap "menang" atau "kalah" akan dicapkan pada sebuah kotak. Kotak yang sama tidak akan dicap $2$ kali. Kartu poin yang memiliki cap menang pada setidaknya $N$ kotak dari $2N$ kotak dapat ditukarkan dengan hadiah. Selain itu, cap pada kartu poin dapat diubah dengan biaya $1$ yen per $1$ kotak.
JOI-kun memiliki $M$ lembar kartu poin yang seluruh $2N$ kotaknya sudah terisi penuh. Pada kartu poin $i$ ($1 \le i \le M$), terdapat $A_i$ cap menang dan $B_i$ cap kalah. JOI-kun menginginkan setidaknya $M - 1$ hadiah.
Tentukan biaya minimum yang diperlukan agar JOI-kun dapat memperoleh setidaknya $M - 1$ hadiah.
Format Masukan
Masukan terdiri dari $M + 1$ baris.
Pada baris ke-$1$, tertulis $2$ bilangan bulat $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) yang dipisahkan oleh spasi. Hal ini menyatakan bahwa setiap kartu poin memiliki $2N$ kotak dan JOI-kun memiliki $M$ lembar kartu poin.
Pada baris ke-$i$ ($1 \le i \le M$) dari $M$ baris berikutnya, masing-masing tertulis $2$ bilangan bulat $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), yang menyatakan bahwa pada kartu poin $i$ terdapat $A_i$ cap menang dan $B_i$ cap kalah.
Format Keluaran
Keluarkan biaya minimum yang diperlukan agar JOI-kun memperoleh setidaknya $M - 1$ hadiah dalam $1$ baris.
Contoh Masukan dan Keluaran
Contoh Masukan 1
4 5 1 7 6 2 3 5 4 4 0 8
Contoh Keluaran 1
4
Contoh Masukan 2
5 4 5 5 8 2 3 7 8 2
Contoh Keluaran 2
0
Pada Contoh Masukan 1, jika JOI-kun mengubah $3$ cap kalah pada kartu poin $1$ menjadi cap menang dan mengubah $1$ cap kalah pada kartu poin $3$ menjadi cap menang, maka dengan $4$ yen terdapat $4$ ($= 5 - 1$) kartu yang dapat ditukarkan dengan hadiah, dan ini adalah biaya minimum.
Pada Contoh Masukan 2, karena sudah ada $3$ ($= 4 - 1$) kartu yang dapat ditukarkan dengan hadiah, maka tidak perlu mengubah cap apa pun.