K - パンプキン
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
黒猫のスヌケ君は「パンプキン2」というカードゲームで遊んでいます。
そこでスヌケ君は以下のような問題を考えることにしました。
今、スヌケ君の手元に N 枚のカードがあります。 i 番目のカードのコストは C_i、ゲインは G_i です。
スヌケ君は各カードについて以下のどちらかの操作を 1 度だけ行うことができます。
- 抽出:カードのゲインの値だけマナが増える。ただし、スヌケ君が最初に持っているマナは 0 である。
- 召喚:カードのコストの値だけマナを消費することによって、そのカードを召喚することができる。ただし、マナが足りない場合は召喚を行うことはできない。
操作を行うカードは好きな順番で選ぶことができます。
このとき、スヌケ君が召喚できるカードは最大で何枚でしょうか?
制約
- 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
出力
スヌケ君が召喚できるカードの枚数の最大値を出力せよ。
入力例 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 枚も召喚できません。