AT_cf17_final_d Zabuton
Description
[problemUrl]: https://atcoder.jp/contests/cf17-final/tasks/cf17_final_d
ある年のCODE FESTIVALの本戦には $ N $ 人の参加者が集まりました。 参加者 $ i $ は身長が $ H_i $ で力が $ P_i $ です。
りんごさんは参加者に座布団を積むゲームをしてもらおうとしています。
参加者は好きな順番で並び、$ 1 $ 人ずつ座布団を $ 1 $ 箇所に積んでいきます。 はじめ、座布団は $ 1 $ 枚も積まれていません。 参加者 $ i $ は、自分の番が回ってきた時にすでに積まれた座布団が $ H_i $ 枚以下の場合はちょうど $ P_i $ 枚の座布団を積みます。そうでない場合は諦めて $ 1 $ 枚も積みません。
りんごさんはできるだけ多くの参加者に座布団を積んで欲しいと思っています。 参加者の並び順を工夫することによって、最大で何人の参加者に座布団を積んでもらうことができるでしょうか?
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 1\ \leq\ N\ \leq\ 5000 $
- $ 0\ \leq\ H_i\ \leq\ 10^9 $
- $ 1\ \leq\ P_i\ \leq\ 10^9 $
### Sample Explanation 1
入力の通りの順に参加者が並ぶと、$ 1,3 $ 番目の参加者が座布団を積むことができます。 また、$ 3 $ 人全員が座布団を積めるような並び順は存在しないため、答えは $ 2 $ 人となります。
### Sample Explanation 2
$ 2 $ 番、$ 3 $ 番、$ 1 $ 番の順で参加者が並ぶと、全員が座布団を積むことができます。