题目描述

小 B 收集了 $m$ 张积分卡。每张卡恰有 $2n$ 个格子，所有格子都已盖章，其中有 $A_i$ 个成功章和 $B_i$ 个失败章，满足 $A_i+B_i=2n$。

一张卡上的成功章至少达到 $n$ 个，就能兑换一份奖品。小 B 可以花费 $1$ 枚金币，把任意一个失败章改为成功章；一个格子最多修改一次。

他希望至少有 $m-1$ 张卡能够兑换奖品。请计算最少需要花费多少枚金币。卡片之间的印章不能转移。如果原本已经满足目标，可以不做修改。

输入格式

第一行两个整数 $n,m$，分别表示一半的格子数和卡片数量。

接下来 $m$ 行，每行两个整数 $A_i,B_i$，描述第 $i$ 张卡上的成功章数和失败章数。

输出格式

输出一个整数，表示达到目标的最少花费。

样例

3 4
1 5
3 3
0 6
5 1

2

2 1
0 4

0

5 3
0 10
0 10
5 5

5

样例解释

样例 1

四张卡分别需要补 $2,0,3,0$ 个成功章。放弃第三张卡，只补第一张的两个章，便有三张达标，花费 $2$。

样例 2

目标是至少 $m-1=0$ 张达标，不需要修改。

样例 3

前两张各需补 $5$ 个章，第三张已经达标。只需补前两张中的任意一张，即可让两张达标。

数据范围与约定

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