題目描述

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$）張集點卡可兌換獎品，因此不需要請人改寫印章。