连环爆炸
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

星穹铁道,启动!

希儿打怪,对面是n个自爆怪。每个怪有a_ib_i两个参数,a_i代表这个怪物的血量,b_i代表这个怪物身亡后自爆对所有单体怪物造成的伤害。

你可以选择任意怪物,进行“手动消灭”,将其血量变为0。

当一个怪物由于“手动消灭”或其他怪物的自爆,血量变为0及0以下,则该怪物被消灭,并对所有单体怪物造成b_i的伤害。

问最少“手动消灭”几个怪物能消灭所有怪物。

注意:这些怪是可以通过怪的自爆连续引爆的。

输入描述:

第一行一个正整数n,表示怪物的数量。

接下来的n行,每行两个正整数a_ib_i。(a_i代表这个怪物的血量,b_i代表这个怪物身亡后自爆对所有单体怪物造成的伤害)

1≤n≤4000

1≤a_i≤1000000000

1≤b_i≤250000 

输出描述:

输出一个正整数,表示能消灭所有怪物的最少使用“手动消灭”的次数。
示例1

输入

复制
5
4 2
6 2
7 2
8 2
10 2

输出

复制
2
示例2

输入

复制
5
4 2
6 2
7 100
8 2
10 2

输出

复制
1