Умова задачі

На торговій вулиці 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$) картки можна обміняти на призи, тому переписувати нічого не потрібно.