奇迹之门
题面描述
你接触到了一款叫做 Doors of Wonder 的游戏。在这款游戏中，有一个由 扇门组成的地图。门的编号由 开始，一直到 。你一开始拥有 个金币，你要通过开门来获得或失去金币。
第 扇门初始就是开着的，其他的都是锁着的。对于 从 到 ，第 扇门拥有两个参数 ，表示打开第 扇门后你会获得 个金币（若 为负表示你需要付出 个金币才能打开这扇门），并且这扇门的唯一钥匙放在第 扇门后。也就是说，你要打开第 扇门后，你才能打开第 扇门。
在任意时刻，你拥有的金币数量都必须非负。并且，你可以在任意时刻选择离开这里，停止开门。你还可以任意选择开门的顺序。那么，你最多能赚到多少金币呢？
输入格式
第一行两个整数 ，表示房间的数量 ，初始的金币数量。
接下来 行，第 行包含两个整数 ，表示打开第 扇门的收益、第 扇门的钥匙的位置。
输出格式
一行一个整数表示能赚到的最多的金币数量。也就是最大的金币数量减去初始的金币数量。
样例
5 0
1 0
-100 0
10000 2
10000 2
1 1
2
说明/提示
你可以先打开第 扇门，这样你拥有 个金币。随后你可以打开第 扇门，这样你拥有了 个金币。
你无法打开第 扇门，因为它们的钥匙在第 扇门后，而你无法拥有 个金币来打开第 扇门。
对于 的数据，。初始的金币数 满足 。对于所有的 ，有 ，。
国庆提高/省选组比赛
- Status
- Live... (Attended)
- Rule
- IOI
- Problem
- 40
- Start at
- 2025-10-15 19:32
- End at
- 2025-11-16 0:00
- Duration
- 1104 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 85