题目描述

ある年のCODE FESTIVALの本戦には $N$ 人の参加者が集まりました。 参加者 $i$ は身長が $H_i$ で力が $P_i$ です。

りんごさんは参加者に座布団を積むゲームをしてもらおうとしています。

参加者は好きな順番で並び、$1$ 人ずつ座布団を $1$ 箇所に積んでいきます。 はじめ、座布団は $1$ 枚も積まれていません。 参加者 $i$ は、自分の番が回ってきた時にすでに積まれた座布団が $H_i$ 枚以下の場合はちょうど $P_i$ 枚の座布団を積みます。そうでない場合は諦めて $1$ 枚も積みません。

りんごさんはできるだけ多くの参加者に座布団を積んで欲しいと思っています。 参加者の並び順を工夫することによって、最大で何人の参加者に座布団を積んでもらうことができるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $H_1$ $P_1$ $H_2$ $P_2$ $:$ $H_N$ $P_N$

输出格式

座布団を積む参加者の人数の最大値を出力せよ。

题目大意

有 $N$ 个人，他们按一定顺序排成一队，依次向砖堆中加砖。
对于第 $i$ 个人，如果此时砖堆中有 $\leq H_i$ 块砖，他就会往砖堆中加入 $P_i$ 块砖，否则他会什么也不做。

一开始砖堆中有 $0$ 块砖，即没有。

你可以任意安排这些选手加砖的顺序，求出最多能够让多少人往砖堆中加入砖。

3
0 2
1 3
3 4

2

3
2 4
3 1
4 1

3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

5

提示

制約

• $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$ 番の順で参加者が並ぶと、全員が座布団を積むことができます。