问题

JOI商店街提供积分卡服务。每张积分卡有 $2N$ 个格子。购买商品后，可以抽奖，根据结果会在格子上标记“中奖”或“未中奖”。同一个格子不会被标记两次。有 $N$ 个以上格子上有“中奖”标记的积分卡可以兑换奖品。而且，可以按照每个格子 $1$ 元的价格更改积分卡上的标记。

JOI君有 $M$ 张所有格子都被填满的积分卡。积分卡 $i$ ($1 \leqq i \leqq M$) 上有 $A_i$ 个“中奖”标记和 $B_i$ 个“未中奖”标记。JOI君想要至少 $M - 1$ 个奖品。

求得到至少 $M - 1$ 个奖品所需的最小费用。

输入

输入包含 $M + 1$ 行。

第一行有两个整数 $N, M$ ($1 \leqq N \leqq 1,000$，$1 \leqq M \leqq 1,000$)，用空格分隔。表示积分卡有 $2N$ 个格子，JOI君有 $M$ 张积分卡。

接下来的 $M$ 行中，第 $i$ 行 ($1 \leqq i \leqq M$) 有两个整数 $A_i, B_i$ ($0 \leqq A_i \leqq 2N$，$0 \leqq B_i \leqq 2N$，$A_i + B_i = 2N$)。表示积分卡 $i$ 上有 $A_i$ 个“中奖”标记和 $B_i$ 个“未中奖”标记。

输出

输出至少 $M - 1$ 个奖品所需的最小费用。

示例 1

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

输出示例 1

4

在示例 1 中，将积分卡 1 上的 3 个“未中奖”标记改成“中奖”标记，并将积分卡 3 上的 1 个“未中奖”标记改成“中奖”标记，总共花费 4 元，就可以用 4 张（$= 5 - 1$）卡片兑换奖品，这是最小的费用。

示例 2

5 4
5 5
8 2
3 7
8 2

输出示例 2

0

在示例 2 中，已经有 3（$= 4 - 1$）张卡可以兑换奖品了，不需要改动。