题目描述
【题目背景】
乘隙插足,扼其主机,渐之进也。
炉石传说回归了,Jaggerchan 最近很喜欢玩。有一天他玩腻了,分解了自己的所有卡牌(即一张卡牌都没有),并希望 33DAI 帮他尽可能消耗掉自己的“奥术之尘”。
炉石传说有 $m$ 种卡牌,第 $i$ 种卡牌的合成价格是 $a_i$,分解价格是 $b_i$。Jaggerchan 现在有 $n$ 个奥术之尘,$0$ 张卡牌。33DAI 可以进行两种操作(任意次数,包括 $0$ 次):
1. 如果奥术之尘数量大于等于 $a_i$,那么它可以合成一次第 $i$ 种卡牌,这会使他的奥术之尘减少 $a_i$,并得到一张第 $i$ 种卡牌。
2. 如果他合成过至少一张第 $i$ 种卡牌,那么它可以分解一张第 $i$ 种卡牌,这会使他的奥术之尘增加 $b_i$,并减少一张第 $i$ 种卡牌。
Jaggerchan 一张卡牌都不想要,请问在最终卡牌数量为 $0$ 的基础上,33DAI 最多能消耗掉多少奥术之尘,请输出 Jaggerchan 剩余奥术之尘的最小值。
输入
第一行为空格隔开的两个数 $n,m$。
接下来 $m$ 行,第 $i$ 行为空格隔开的 $a_i,b_i$。
输出
输出 Jaggerchan 剩余奥术之尘的最小值。
样例输入输出
提示
【样例1解释】
只要当前奥术之尘大于等于 $2$ 就可以执行一次合成,然后立马分解,最后就会剩下 $1$ 的奥术之尘。
【样例3解释】
可以先合成并分解一张第 $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 分):没有特殊限制。