← 返回题目列表

AtCoder · jag2017summer_day1_k

K. 南瓜

中文机器翻译题面 查看原题

問題文

黑猫的su努克君正在玩一款名为《南瓜2》的卡牌游戏。

于是,su努克君决定思考如下问题。

现在,su努克君手头有 N 张卡片。 i 第个卡片的成本 需要是 您也可以写 C_i、收益因是 您也可以写 G_i 。

suke君可以对每张卡牌进行以下两种操作中的一种 1 次。

  • 抽取:增加卡牌收益值法力值。但是,sukuke君最初拥有的法力值为 0 。
  • 召唤:消耗卡牌费用值的法力值后,可以召唤该卡牌。但是,法力值不足时无法进行召唤。

可以按照自己喜欢的顺序选择进行操作的卡牌。

此时,suke君最多可以召唤多少张卡牌?

制約

  • 1≦N≦10^5
  • 0≦C_i≦10^9
  • 0≦G_i≦10^9

入力

输入是按以下格式从标准输入给出的。

N
C_1 G_1
C_2 G_2
:
C_N G_N

出力

输出suke君能够召唤的卡牌数量的最大值。


入力例 1

5
3 0
0 4
2 1
2 0
1 3

出力例 1

3

例如,执行如下操作,3 张卡牌即可召唤。

  • 5 抽取第张卡牌。法力值为 3 增加为。
  • 3 召唤第张卡牌。法力值为 1 减少到。
  • 2 抽取第张卡牌。法力值为 5 增加为。
  • 1 召唤第张卡牌。法力值为 2 减少到。
  • 4 召唤第张卡牌。法力值为 0 减少到。

入力例 2

7
1 0
2 1
3 1
3 2
3 2
4 0
5 5

出力例 2

3

入力例 3

1
1 0

出力例 3

0

对于此输入, 1 连一张也无法召唤。