海的对面,是敌人!!
题号：NC219630
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

n个巨人来到帕岛门前,围成一个圈,顺时针编号为1,2,3,...n

第i个巨人有hp_i的生命值,有bo_i的重量

当第i个巨人死亡时(死亡表示)

这个巨人会倒向第k 个巨人(如果 i < n那么 k = i + 1 ,如果 i = = n ,那么k = 1 ),对第k个巨人造成 bo_i 的伤害

如果第 k 个巨人受到伤害后挂了,会倒向下一个巨人...当然下一个巨人死后可能又会倒向下一个巨人.......

现在笠笠笠每次出手可以对任意一个巨人造成1点伤害

请你设计一个最优策略让笠笠笠出手次数最少,就能干掉所有巨人。

输入描述:

第一行一个数n

接下来n行,第i行两个数字分别是hp_i和bo_i

输出描述:

一个数,表示笠笠笠为了干掉所有巨人出手的最小次数。
示例1

输入

复制 
3
1 2
3 4
5 6

输出

复制 
3

说明

先打第一个巨人,那么第一个巨人会死,对第二个巨人造成2点伤害,此时三个巨人血量分别是[0,1,5]

再打第二个巨人,第二个巨人也会死,对第三个巨人造成4点伤害,此时三个巨人血量分别是[0,0,1]

再打第三个巨人,第三个巨人也会死,然后会对第一个巨人造成6点伤害,然而第一个巨人已经死了,就不会再发生连锁反应。

不过没关系,所有巨人都挂了,共出手三次,可以证明这是一种最优的策略。

备注: