题目描述
有一家牧场,每天都会产出牛奶,在第 $i$ 天,牛奶的产量为 $p_i$。商人每天都会发来一张订单,在第 $i$ 天,商人的订单收购量为 $c_i$,每天多余的牛奶会被保存下来加入库存中。
牧场收到订单时,可以忽略该订单,以满足其他订单需求。当然如果想要完成订单,则库存中必须需要足够的牛奶供应给商人,反之若牛奶量不够,则无法完成订单。
现给定$n$天,每天的牛奶的产量与订单的需求量,问牧场主最多满足多少张订单。
输入
输入第一行:一个正整数,表示$n$
接下来$n$行:每行两个正整数$p_i,c_i$,表示第$i$天的牛奶的产量与订单的需求量。
输出
输出一个正整数,表示最多能满足的订单的数量
样例输入输出
输入#1
复制
4
10 7
3 5
1 8
2 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张订单。