题目描述

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$）张积分卡可以兑换奖品，所以不需要改写任何印章。