題目描述

JOI 商店街提供緊積分卡服務。每張積分卡有 $2N$ 個格仔。買嘢嗰陣可以抽獎，根據結果會喺格仔上面蓋上「中獎」或者「唔中獎」嘅印仔。同一個格仔唔會被蓋 $2$ 次印仔。喺 $2N$ 個格仔入面，有至少 $N$ 個格仔蓋咗中獎印仔嘅積分卡，就可以換領獎品。另外，積分卡上面嘅印仔可以用每 $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$ 張積分卡。

喺接住落嚟 $M$ 行入面嘅第 $i$ 行（$1 \le i \le 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$）張卡可以換領獎品，所以唔需要改寫任何印仔。