Условие задачи

На торговой улице JOI действует система бонусных карт. На каждой бонусной карте есть $2N$ клеточек. При покупке товара можно вытянуть жребий, и в зависимости от результата в клеточку ставится печать «выигрыш» или «промах». В одну и ту же клеточку печать никогда не ставится $2$ раза. Бонусную карту, на которой печать выигрыша стоит хотя бы в $N$ клеточках из $2N$, можно обменять на приз. Кроме того, печать на бонусной карте можно переделать за $1$ иену в расчёте на $1$ клеточку.

У JOI-куна есть $M$ бонусных карт, в которых заполнены все $2N$ клеточек. На бонусной карте $i$ ($1 \le i \le M$) стоит $A_i$ печатей выигрыша и $B_i$ печатей промаха. JOI-кун хочет получить не менее $M - 1$ призов.

Найдите минимальную стоимость, необходимую JOI-куну для получения не менее $M - 1$ призов.

Входные данные

Входные данные состоят из $M + 1$ строк.

В строке $1$ через пробел записаны $2$ целых числа $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$). Это означает, что на бонусной карте $2N$ клеточек и у JOI-куна есть $M$ бонусных карт.

В $i$-й строке ($1 \le i \le M$) из следующих $M$ строк записаны соответственно по $2$ целых числа $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), означающие, что на бонусной карте $i$ проставлено $A_i$ печатей выигрыша и $B_i$ печатей промаха.

Выходные данные

Выведите в $1$ строке минимальную стоимость, необходимую JOI-куну для получения не менее $M - 1$ призов.

Примеры ввода и вывода

Пример ввода 1

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

Пример вывода 1

4

Пример ввода 2

5 4
5 5
8 2
3 7
8 2

Пример вывода 2

0

В примере ввода 1, если на бонусной карте $1$ переделать $3$ печати промаха в печати выигрыша, а на бонусной карте $3$ переделать $1$ печать промаха в печать выигрыша, то за $4$ иены $4$ ($= 5 - 1$) карты станут доступны для обмена на призы, и это минимальная стоимость.

В примере ввода 2 уже $3$ ($= 4 - 1$) карты можно обменять на призы, поэтому ничего переделывать не нужно.