Problema

La calle comercial JOI ofrece un servicio de tarjetas de puntos. Cada tarjeta de puntos tiene $2N$ casillas. Al comprar un producto, se puede participar en un sorteo y, según el resultado, se estampa un sello de «premio» o «sin premio» en una casilla. Nunca se estampa un sello $2$ veces en la misma casilla. Una tarjeta de puntos que tenga sellos de premio en al menos $N$ de las $2N$ casillas se puede canjear por un regalo. Además, se puede pedir que cambien el sello de una tarjeta de puntos por $1$ yen por cada $1$ casilla.

JOI-kun tiene $M$ tarjetas de puntos en las que las $2N$ casillas están completamente llenas. En la tarjeta de puntos $i$ ($1 \le i \le M$), hay $A_i$ sellos de premio y $B_i$ sellos sin premio. JOI-kun quiere conseguir al menos $M - 1$ regalos.

Halla el costo mínimo necesario para que JOI-kun obtenga al menos $M - 1$ regalos.

Entrada

La entrada consta de $M + 1$ líneas.

En la línea $1$ están escritos $2$ enteros $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) separados por un espacio. Esto indica que cada tarjeta de puntos tiene $2N$ casillas y que JOI-kun tiene $M$ tarjetas de puntos.

En la línea $i$ ($1 \le i \le M$) de las siguientes $M$ líneas están escritos respectivamente $2$ enteros $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), lo que indica que la tarjeta de puntos $i$ tiene estampados $A_i$ sellos de premio y $B_i$ sellos sin premio.

Salida

Imprime en $1$ línea el costo mínimo necesario para que JOI-kun obtenga al menos $M - 1$ regalos.

Ejemplo de entrada y salida

Ejemplo de entrada 1

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

Ejemplo de salida 1

4

Ejemplo de entrada 2

5 4
5 5
8 2
3 7
8 2

Ejemplo de salida 2

0

En el ejemplo de entrada 1, si en la tarjeta de puntos $1$ se cambian $3$ sellos sin premio por sellos de premio y en la tarjeta de puntos $3$ se cambia $1$ sello sin premio por un sello de premio, por $4$ yenes habrá $4$ ($= 5 - 1$) tarjetas canjeables por regalos, y este es el costo mínimo.

En el ejemplo de entrada 2, como ya hay $3$ ($= 4 - 1$) tarjetas canjeables por regalos, no es necesario cambiar ningún sello.