分数: 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