Problema

La via commerciale JOI offre un servizio di carte fedeltà. Ogni carta fedeltà ha $2N$ caselle. Quando si acquista un prodotto, si può estrarre a sorte un biglietto e, a seconda del risultato, viene apposto un timbro "vincente" oppure "non vincente" su una casella. Non viene mai apposto un timbro $2$ volte sulla stessa casella. Una carta fedeltà che presenta il timbro vincente in almeno $N$ delle $2N$ caselle può essere scambiata con un premio. Inoltre, è possibile far modificare il timbro di una carta fedeltà al costo di $1$ yen per $1$ casella.

JOI-kun possiede $M$ carte fedeltà in cui tutte le $2N$ caselle sono piene. Sulla carta fedeltà $i$ ($1 \le i \le M$) sono impressi $A_i$ timbri vincenti e $B_i$ timbri non vincenti. JOI-kun vorrebbe ottenere almeno $M - 1$ premi.

Trova il costo minimo necessario affinché JOI-kun ottenga almeno $M - 1$ premi.

Input

L'input è composto da $M + 1$ righe.

Sulla riga $1$ sono scritti $2$ interi $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) separati da uno spazio. Ciò indica che ogni carta fedeltà ha $2N$ caselle e che JOI-kun possiede $M$ carte fedeltà.

Sulla riga $i$ ($1 \le i \le M$) delle successive $M$ righe sono scritti rispettivamente $2$ interi $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), ad indicare che sulla carta fedeltà $i$ sono impressi $A_i$ timbri vincenti e $B_i$ timbri non vincenti.

Output

Stampa su $1$ riga il costo minimo necessario affinché JOI-kun ottenga almeno $M - 1$ premi.

Esempi di input e output

Esempio di input 1

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

Esempio di output 1

4

Esempio di input 2

5 4
5 5
8 2
3 7
8 2

Esempio di output 2

0

Nell'esempio di input 1, facendo modificare $3$ timbri non vincenti della carta fedeltà $1$ in timbri vincenti e $1$ timbro non vincente della carta fedeltà $3$ in timbro vincente, con $4$ yen si rendono scambiabili con un premio $4$ ($= 5 - 1$) carte, e questo è il costo minimo.

Nell'esempio di input 2, poiché $3$ ($= 4 - 1$) carte sono già scambiabili con un premio, non c'è bisogno di far modificare alcun timbro.