Énoncé du problème

La rue commerçante JOI propose un service de cartes de fidélité. Chaque carte comporte $2N$ cases. Lorsqu'on achète un article, on peut tirer au sort et, selon le résultat, un tampon « gagnant » ou « perdant » est apposé sur une case. Une même case n'est jamais tamponnée $2$ fois. Une carte comportant un tampon gagnant sur au moins $N$ cases parmi les $2N$ cases peut être échangée contre un cadeau. De plus, il est possible de faire modifier un tampon sur une carte au tarif de $1$ yen pour $1$ case.

JOI-kun possède $M$ cartes dont les $2N$ cases sont toutes remplies. Sur la carte $i$ ($1 \le i \le M$), il y a $A_i$ tampons gagnants et $B_i$ tampons perdants. JOI-kun souhaite obtenir au moins $M - 1$ cadeaux.

Déterminez le coût minimal nécessaire pour que JOI-kun obtienne au moins $M - 1$ cadeaux.

Entrée

L'entrée se compose de $M + 1$ lignes.

Sur la ligne $1$ sont écrits $2$ entiers $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) séparés par un espace. Cela indique que chaque carte comporte $2N$ cases et que JOI-kun possède $M$ cartes.

Sur la ligne $i$ ($1 \le i \le M$) des $M$ lignes suivantes sont écrits $2$ entiers $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), indiquant que la carte $i$ comporte $A_i$ tampons gagnants et $B_i$ tampons perdants.

Sortie

Affichez sur $1$ ligne le coût minimal nécessaire pour que JOI-kun obtienne au moins $M - 1$ cadeaux.

Exemples d'entrée et de sortie

Exemple d'entrée 1

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

Exemple de sortie 1

4

Exemple d'entrée 2

5 4
5 5
8 2
3 7
8 2

Exemple de sortie 2

0

Dans l'exemple d'entrée 1, si JOI-kun fait remplacer $3$ tampons perdants de la carte $1$ par des tampons gagnants et $1$ tampon perdant de la carte $3$ par un tampon gagnant, alors pour $4$ yens, $4$ ($= 5 - 1$) cartes deviennent échangeables contre un cadeau, ce qui représente le coût minimal.

Dans l'exemple d'entrée 2, comme $3$ ($= 4 - 1$) cartes sont déjà échangeables contre un cadeau, il n'est pas nécessaire de faire modifier de tampon.