问题 5546 --牛奶供应(二)

5546: 牛奶供应(二)

题目描述

有一家牧场,每天都会产出牛奶,在第 $i$ 天,牛奶的产量为 $p_i$。商人每天都会发来一张订单,在第 $i$ 天,商人的订单收购量为 $c_i$,每天多余的牛奶会被保存下来加入库存中。 牧场收到订单时,可以忽略该订单,以满足其他订单需求。当然如果想要完成订单,则库存中必须需要足够的牛奶供应给商人,反之若牛奶量不够,则无法完成订单。 现给定$n$天,每天的牛奶的产量与订单的需求量,问牧场主最多满足多少张订单。

输入

输入第一行:一个正整数,表示$n$ 接下来$n$行:每行两个正整数$p_i,c_i$,表示第$i$天的牛奶的产量与订单的需求量。

输出

输出一个正整数,表示最多能满足的订单的数量

样例输入输出

输入#1 复制
4
10 7
3 5
1 8
2 3
输出#1 复制
3

提示

对于$30\%$数据:$1 \leq n \leq 10^3$ 对于$70\%$数据:$1 \leq n \leq 10^4$ 对于$100\%$数据:$1 \leq n \leq 10^5$,$1 \leq p_i,c_i \leq 10^4$ 样例1说明:第1张订单满足,此时库存为3 第2张订单满足,此时库存为1 忽略第3张订单,此时库存为2 第4张订单满足,共满足3张订单。
序号 标题 作者 发表时间 费用 订购数 操作