#2259. 反客为主

反客为主

题目背景

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

题目描述

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

炉石传说有 mm 种卡牌,第 ii 种卡牌的合成价格是 aia_i,分解价格是 bib_i。陈老师 现在有 nn 个奥术之尘,00 张卡牌。你 可以进行两种操作(任意次数,包括 00 次):

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

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

输入格式

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

接下来 mm 行,第 ii 行为空格隔开的 ai,bia_i,b_i

输出格式

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

100 1
2 1
1

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

10 1
6 2
2
10 2
6 1
7 3
1

可以先合成并分解一张第 22 种卡牌,剩余尘数变为 107+3=610-7+3=6,然后可以合成并分解一次第 11 种卡牌,剩余尘数变为 66+1=16-6+1=1

数据规模与约定

对于 100%100\% 的数据,1n50001 \le n \le 50001m1001\le m\le 1000bi<ain0\le b_i\lt a_i\le n

  • 子任务 1(10 分):保证 a1=2a_1=2b1=1b_1=1
  • 子任务 2(20 分):保证 m=1m=1
  • 子任务 3(30 分):保证 bi=0b_i=0
  • 子任务 4(40 分):没有特殊限制。