← 返回题目列表

AtCoder · abc187_d

D. 选择我

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

分数: 400 点

问题陈述

AtCoder City 将举行市长选举。候选人是青木和高桥。
该城市由 N 城镇, i- 其中有 A_i 支持青木的选民和 B_i 支持高桥的选民。没有其他选民。
高桥可以在每个城镇发表演讲。
如果他在某个城镇发表演讲,该城镇的所有选民,无论是支持高桥还是支持青木,都会投票给高桥。
另一方面,如果他不在某个城镇发表演讲,则该城镇的亲青木选民将投票给青木,而亲高桥选民将不会投票。
高桥要获得比青木更多的选票,至少需要在多少个城镇发表演讲?

约束

  • 输入中的所有值都是整数。
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i, B_i \le 10^9

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
\vdots
A_N B_N

输出

打印答案。


示例输入 1

4
2 1
2 2
5 1
1 3

示例输出 1

1

在第三镇发表演讲后,青木和高桥将获得 分别投 5 和 6 票。


示例输入 2

5
2 1
2 1
2 1
2 1
2 1

示例输出 2

3

在三个城镇发表演讲后,青木和高桥将获得 4 和 9 票。


示例输入 3

1
273 691

示例输出 3

1