You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

乘隙插足，扼其主机，渐之进也。

题目描述

炉石传说回归了，陈老师 最近很喜欢玩。有一天他玩腻了，分解了自己的所有卡牌（即一张卡牌都没有），并希望 你 帮他尽可能消耗掉自己的“奥术之尘”。

炉石传说有 $m$ 种卡牌，第 $i$ 种卡牌的合成价格是 $a_i$，分解价格是 $b_i$。陈老师 现在有 $n$ 个奥术之尘，$0$ 张卡牌。你 可以进行两种操作（任意次数，包括 $0$ 次）：

1. 如果奥术之尘数量大于等于 $a_i$，那么它可以合成一次第 $i$ 种卡牌，这会使他的奥术之尘减少 $a_i$，并得到一张第 $i$ 种卡牌。
2. 如果他合成过至少一张第 $i$ 种卡牌，那么它可以分解一张第 $i$ 种卡牌，这会使他的奥术之尘增加 $b_i$，并减少一张第 $i$ 种卡牌。

陈老师 一张卡牌都不想要，请问在最终卡牌数量为 $0$ 的基础上，你 最多能消耗掉多少奥术之尘，请输出 陈老师 剩余奥术之尘的最小值。

输入格式

第一行为空格隔开的两个数 $n,m$。

接下来 $m$ 行，第 $i$ 行为空格隔开的 $a_i,b_i$。

输出格式

输出 陈老师 剩余奥术之尘的最小值。

100 1
2 1

1

只要当前奥术之尘大于等于 $2$ 就可以执行一次合成，然后立马分解，最后就会剩下 $1$ 的奥术之尘。

10 1
6 2

2

10 2
6 1
7 3

1

可以先合成并分解一张第 $2$ 种卡牌，剩余尘数变为 $10-7+3=6$，然后可以合成并分解一次第 $1$ 种卡牌，剩余尘数变为 $6-6+1=1$。

数据规模与约定

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

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