AT_abc437_c [ABC437C] Reindeer and Sleigh 2

$ N $ 匹のトナカイと $ 1 $ 個のソリがあります。 $ i $ 番目のトナカイは重さが $ W_i $ で力は $ P_i $ です。 各トナカイについて、「ソリを引く」または「ソリに乗る」のいずれかを選びます。 ただし、ソリを引くトナカイの力の総和が、ソリに乗るトナカイの重さの総和以上でなければなりません。 最大で何匹トナカイをソリに乗せることができますか？ $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ W_1 $ $ P_1 $ $ W_2 $ $ P_2 $ $ \vdots $ $ W_N $ $ P_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ 3 $ 番目のトナカイがソリを引き、 $ 1 $ 番目と $ 2 $ 番目のトナカイがソリに乗ると、ソリを引くトナカイの力の総和は $ P_3=9 $ 、ソリに乗るトナカイの重さの総和は $ W_1+W_2=7 $ となるため条件を満たします。すべてのトナカイがソリに乗ることはできないため、求める答えは $ 2 $ です。 ### Constraints - $ 1\leq T\leq 10^5 $ - $ 1\leq N\leq 3\times 10^5 $ - $ 1\leq W_i,P_i\leq 10^9 $ - 入力は全て整数 - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 3\times 10^5 $ 以下