← 返回题目列表

AtCoder · joi2011ho5

E. 微生物实验(Bug Party)

中文机器翻译题面 查看原题

配点: 100 点

你听说过 Just Odd Inventions 吗?这家公司的业务就是制造“只是奇怪的发明”。在这里,我们将其缩写为J​​OI。

JOI开发了多种微生物。 1 我们正在研究如何在培养皿中活捉动物。待研究微生物 N 有1,2,\ldots,N 。当每种微生物被困在培养皿中时,它会立即向培养皿中释放一种称为 foo(致命奇怪物体)的有害物质。每种微生物释放的 foo 量是已知的。限制在培养皿中的所有微生物释放的 foo 被培养皿中的每种微生物同等地摄入。每种微生物对foo的耐受量是已知的,如果微生物摄入超过这个量的foo,就会死亡。

微生物 i 的 foo 排放量为 a_i 毫克,foo 耐受性为 b_i 毫克。换句话说,培养皿中存在微生物。 当 i_1,i_2,\ldots,i_k 被限制时,培养皿中的每种微生物 \displaystyle \frac{a_{i_1}+a_{i_2}+\cdots+a_{i_k}}k 摄入毫克 foo 后,培养皿中的微生物 i 表示该摄入量是 如果它大于 b_i ,它就会死亡。

受 JOI 委托,您必须在培养皿中捕获尽可能多的活微生物。然而,死亡的微生物会对培养皿内的环境产生负面影响,因此培养皿中的微生物不应通过摄入 foo 来杀死。

JOI如何通过“只是一项奇怪的发明”来获利仍然是一个谜,除了总裁之外,JOI内部没有人知道。

課題

给定要调查的微生物数量、每种微生物的 foo 释放量和 foo 允许量,1 编写一个程序来找出一个培养皿中可以限制的最大微生物数量。

制限

1 \leqq N \leqq 300\,000\,(=3\times 10^5)  待调查微生物数量
1 \leqq a_i \leqq 100\,000\, (=10^5)  微生物 i foo 排放量(毫克)
1 \leqq b_i \leqq 100\,000\, (=10^5)  微生物 i foo 津贴(毫克)

入力

从标准输入读取以下输入。

  • 1 行是一个整数 写为 N ,待研究的微生物为 N 表示有 1 个。
  • 继续 N 行包含有关每种微生物的信息。i + 1 行目 (1\leqq i\leqq N) 是正整数 a_i,b_i 以空格作为分隔符,微生物为 i 的 foo 排放量为 a_i foo 耐受性(毫克) b_i 表示毫克。

出力

在标准输出上,1 一个培养皿中可限制的最大微生物数量。 输出为 1 行。

注意

在这个问题中,要处理的整数范围是 32 请注意,它可能不适合该位。

採点基準

评分数据中,分配的分数 30 对于%,N\leqq 1\,000 满意。


入力例 1

6
12 8
5 9
2 4
10 12
6 7
13 9

出力例 1

3

在此示例中,微生物 如果将 2, 4, 5 放入培养皿中,则释放的 foo 总量为 5 + 10 + 6 = 21 毫克,每种微生物摄入的foo量为 \displaystyle \frac{21}3=7 毫克。微生物 2, 4, 5 的 foo 容差是 9, 12, 7 由于它是毫克,因此不会杀死培养皿中的任何微生物。另外,4 不可能在培养皿中放入超过一种微生物而不杀死任何微生物。