미생물 실험 (Bug Party)

Just Odd Inventions 사(줄여서 JOI 사)는 "그저 기묘한 발명(just odd inventions)"을 하는 회사로, 여러 미생물을 하나의 샬레(배양 접시)에 살아 있는 채로 가두는 연구를 하고 있다.

조사 대상 미생물은 $N$마리이며 $1, 2, \dots, N$의 번호가 붙어 있다. 각 미생물은 샬레에 갇히면 즉시 foo(fatally odd object)라는 유해 물질을 샬레 안에 방출한다. 샬레에 갇힌 모든 미생물이 방출한 foo는 샬레 안의 각 미생물이 균등하게 흡수한다. 각 미생물에는 foo 허용량이 있으며, 이 양을 초과해 foo를 흡수하면 그 미생물은 죽는다.

미생물 $i$의 foo 방출량은 $a_i$ 밀리그램, foo 허용량은 $b_i$ 밀리그램이다. 즉 미생물 $i_1, i_2, \dots, i_k$를 샬레에 가두면 각 미생물은 $(a_{i_1} + a_{i_2} + \dots + a_{i_k}) / k$ 밀리그램의 foo를 흡수하고, 이 흡수량이 자신의 허용량 $b_i$보다 크면 죽는다.

가능한 한 많은 미생물을 살아 있는 채로 샬레에 가두어야 한다. 단, 죽은 미생물의 사체는 샬레 내부 환경에 악영향을 주므로 샬레 안의 어떤 미생물도 foo 흡수로 죽어서는 안 된다.

미생물 수와 각 미생물의 foo 방출량 및 허용량이 주어질 때, 하나의 샬레에 가둘 수 있는 미생물 수의 최댓값을 구하여라.

• 첫 번째 줄에 미생물 수를 나타내는 정수 $N$이 주어진다.
• 이어지는 $N$개의 줄 중 $i$번째 줄에는 공백으로 구분된 두 양의 정수 $a_i$, $b_i$가 주어지며, 이는 미생물 $i$의 foo 방출량이 $a_i$ 밀리그램, foo 허용량이 $b_i$ 밀리그램임을 나타낸다.

하나의 샬레에 가둘 수 있는 미생물 수의 최댓값을 한 줄에 출력한다.

• $1 \le N \le 300000$ — 조사 대상 미생물의 수
• $1 \le a_i \le 100000$ — 미생물 $i$의 foo 방출량(밀리그램)
• $1 \le b_i \le 100000$ — 미생물 $i$의 foo 허용량(밀리그램)

방출량의 합이 32비트 정수 범위를 넘을 수 있으므로 64비트 정수를 사용해야 한다.

샘플 입력(미생물 6마리)에서는 미생물 2, 4, 5를 샬레에 넣으면 방출되는 foo의 합이 $5 + 10 + 6 = 21$ 밀리그램이고, 각 미생물이 흡수하는 foo의 양은 $21 / 3 = 7$ 밀리그램이 된다. 미생물 2, 4, 5의 허용량은 각각 $9, 12, 7$ 밀리그램이므로 어떤 미생물도 죽지 않는다. 또한 어떤 미생물도 죽지 않도록 4마리 이상을 샬레에 넣는 것은 불가능하다.