Choose Me

题目描述

AtCoder City 将举行市长选举。候选人是 Aoki 和 Takahashi。
这个城市由 $N$ 个城镇组成，第 $i$ 个城镇有 $A_i$ 名支持 Aoki 的选民和 $B_i$ 名支持 Takahashi 的选民。没有其他选民。
Takahashi 可以在每个城镇发表演讲。
如果他在某个城镇发表演讲，该城镇的所有选民（无论支持 Takahashi 还是 Aoki）都会投票给 Takahashi。
另一方面，如果他没有在某个城镇发表演讲，该城镇中支持 Aoki 的选民将投票给 Aoki，而支持 Takahashi 的选民将不会投票。
为了获得比 Aoki 更多的选票，Takahashi 至少需要在多少个城镇发表演讲？

输入格式

输入通过标准输入按如下格式给出： $N$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$

输出格式

输出答案。

4
2 1
2 2
5 1
1 3

1

5
2 1
2 1
2 1
2 1
2 1

3

1
273 691

1

提示

All values in input are integers. $1 \le N \le 2 \times 10^5$ $1 \le A_i, B_i \le 10^9$在第三个城镇发表演讲后，Aoki 和 Takahashi 将分别获得 $5$ 和 $6$ 票。
在三个城镇发表演讲后，Aoki 和 Takahashi 将分别获得 $4$ 和 $9$ 票。

标签: AtCoder|abc187D

来源

AtCoder|abc187D