题目描述

起初有 $n$ 个单位的毒素，可以通过 合成/分解 $m$ 种新物质的措施减少毒素。具体而言就是 $a_i$ 单位的毒素可以合成一个单位的第 $i$ 种物质，分解一个单位的第 $i$ 种物质将会产生 $b_i$ 单位的毒素，你可以将这个过程重复多次。当然最后不允许存在 $m$ 种物质中的任何一种。

求最终剩余毒素的数量的最小值。

输入格式

第一行，两个正整数 $n$ 和 $m$。

接下来 $m$ 行，第 $i$ 行两个整数 $a_i$ 和 $b_i$。

输出格式

一个整数，意义如题所述。

样例

输入数据 #1

100 1
2 1

输出数据 #1

1

解释 #1

只要毒素数量不小于 $2$ 就可以执行一次合成，然后立刻分解，重复这个操作，最终毒素剩余值为 $1$ 。

$$100 - 2 + 1 = 99 \\ 99 - 2 + 1 = 98 \\ \ldots \\ 3 - 2 + 1 = 2 \\ 2 - 2 + 1 = 1$$

输入数据 #2

10 1
6 2

输出数据 #2

2

解释 #2

$$10 - 6 + 2 = 6 \\ 6 - 6 + 2 = 2$$

输入数据 #3

10 2
6 1
7 3

输出数据 #3

1

解释 #3

先合成/分解第 $2$ 种物质，剩余毒素为

$$10 - 7 + 3 = 6$$

再合成/分解第 $1$ 种物质，剩余毒素为

$$6 - 6 + 1 = 1$$

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 5000$，$1 \leq m \leq 100$，$0 \leq b_i < a_i \leq n$。

子任务

1. （$10$ 分）：保证 $a_1 = 2$ 且 $b_1 = 1$。
2. （$20$ 分）：保证 $m = 1$。
3. （$30$ 分）：保证 $b = 0$。
4. （$40$ 分）：没有特殊限制。