该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

大维是一位拉面爱好者，常去心仪的拉面店。最近店里推出了集章活动：每碗拉面可以获得一次抽签机会，并在积分卡的空格上盖“中奖”或“未中”印章。集齐足够多的“中奖”印章，就能兑换免费拉面券。为此，大维需要权衡和付费，将“未中”印章改为“中奖”，以达到兑换条件。

题目描述

每张积分卡共有 $2n$ 个格子。每当顾客购买一碗拉面后，便可抽取一次幸运签，根据结果在任意一个空格上盖上“中奖”或“未中”的印章。每个格子只能被盖一次，不可重复。

当一张积分卡上至少有 $n$ 个“中奖”印章时，即可凭此卡兑换一张免费拉面券。如果某张卡的“中奖”数不足 $n$，也可以选择付费修改：每将一个“未中”印章改为“中奖”，需花费 1 单位费用。

大维已经有了 $m$ 张所有格子都被盖满的积分卡。第 $i$ 张卡上有 $A_i$ 个“中奖”格子，以及 $B_i$ 个“未中”格子（显然 $A_i + B_i = 2n$）。

大维希望能至少兑换 $m-1$ 张拉面券，也就是他可以最多放弃一张积分卡，不进行兑换。请问，为了至少获得 $m-1$ 张拉面券，他最少需要花费多少钱。

输入格式

第一行：两个整数 $n,m$，表示每张卡上有 $2n$ 个格子，以及大维拥有 $m$ 张积分卡。
接下来的 $m$ 行，每行两个整数 $A_i,B_i$，表示第 $i$ 张卡上的“中奖”和“未中”印章数量。

输出格式

输出一行：一个整数，表示大维达成目标所需的最小花费。

样例

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

4

样例解释

对于 $n=4$，每张卡至少需要 $4$ 个“中奖”印章：

• 卡 1：$A_1=1$，需再改 $3$ 个，费用 $3$
• 卡 2：$A_2=6$，已满足，费用 $0$
• 卡 3：$A_3=3$，需再改 $1$ 个，费用 $1$
• 卡 4：$A_4=4$，已满足，费用 $0$
• 卡 5：$A_5=0$，需再改 $4$ 个，费用 $4$

他只需兑换 $5-1=4$ 张卡，故可放弃最昂贵的一张（卡 5），选择费用最小的 4 张：$3+0+1+0=4$。

数据范围

对于 100% 的数据，$1 \le n,m \le 10^5$，$0 \le A_i,B_i \le 2n$，且 $A_i + B_i = 2n$。