卡牌对战游戏
题号:NC207504
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

都非常喜欢卡牌对战游戏,在一次对战游戏中,召唤了个随从,其中第个随从的生命值a_i,攻击力是b_i,现在是的轮次,他需要尽可能降低场攻,有一张名叫“亵渎”的法术牌,在自己的回合开始时,可以指定任意一名的随从,对它发动“亵渎”,该随从会直接死亡。此后,当有随从死亡时,可以继续指定随从发动“亵渎”,但是必须保证指定的随从在上一次死亡随从的右边。当在第轮指定发动“亵渎”的随从,其生命值与上一轮死亡的随从的生命值差值的绝对值不超过时,则第轮指定的随从会死亡。否则,一旦被“亵渎”的随从没有死亡,“亵渎”效果终止。你需要计算的是,当采用最优策略时,最多能降低的场攻是多少。(降低的场攻指所有死亡的随从攻击力之和)

输入描述:

第一行输入,场上随从个数。 
接下来行每行输入两个正整数,表示第个随从的生命值和攻击力。 

输出描述:

输出一行,代表采取最优策略时,最多能够降低的场攻。
示例1

输入

复制
2 5
10 10
16 11

输出

复制
11

说明

\ Bob的最优策略是消灭第二个随从。
示例2

输入

复制
3 2
9 3
7 2
6 1

输出

复制
6

说明

\ Bob可以消灭所有随从。