AT_joi2017yo_b.ポイントカード (Point Card)

在 JOI 商店街，可以通过消费获得印有两种图案的积分卡。每张积分卡上有 $2N$ 个格子，购买商品后，有机会在这些格子上盖上「中奖」或「未中奖」的印章。每个格子最多只会被盖一次。如果一张积分卡上「中奖」印章的数量达到 $N$ 个或更多，则可兑换奖品。此外，每个格子的印章可以花费 $1$ 元钱进行更改。

JOI 君拥有 $M$ 张已经盖满印章的积分卡。第 $i$ 张卡（$1 \leq i \leq M$）上有 $A_i$ 个「中奖」印章和 $B_i$ 个「未中奖」印章。JOI 君想得到至少 $M - 1$ 个奖品。

请计算为了让 JOI 君得到至少 $M - 1$ 个奖品，他所需支付的最小费用。

输入有 $M + 1$ 行。

第 1 行输入两个整数 $N$ 和 $M$，用空格分隔，表示每张积分卡有 $2N$ 个位置，以及 JOI 君持有 $M$ 张卡（$1 \leq N \leq 1000$，$1 \leq M \leq 1000$）。

接下来的 $M$ 行中，第 $i$ 行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 张积分卡上分别有 $A_i$ 个「中奖」印章和 $B_i$ 个「未中奖」印章（$0 \leq A_i \leq 2N$，$0 \leq B_i \leq 2N$，且 $A_i + B_i = 2N$）。

输出一个整数，表示 JOI 君为确保至少 $M - 1$ 张积分卡可以兑换奖品所需的最小费用。

例子说明

在样例 1 中，通过将第 $1$ 张卡片上 $3$ 个「未中奖」印章换为「中奖」，以及将第 $3$ 张卡上 $1$ 个「未中奖」印章换为「中奖」，可以用 $4$ 元钱让 $4$ 张卡（即 $5 - 1$ 张）均可兑换奖品，这是最少花费。

在样例 2 中，已经有 $3$ 张（即 $4 - 1$ 张）积分卡可以兑换奖品，因此不需要进行任何更改。

本翻译由 AI 自动生成