G. 公平买单

Fair Share

时间限制：3 秒 · 内存限制：1024 MiB

原题：NWERC 2025 F · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

$n$ 个人一起用餐，第 $j$ 个人消费了 $b_{j}$ 欧元。如果由其他人刷卡买单，第 $j$ 个人会贡献 $a_{j}$ 欧元现金。餐厅只接受刷卡，而且现在已无法拆分账单。

需要选出一个人，用自己的银行卡支付总账单，并收走其余所有人贡献的现金。被选中的人不再向现金池贡献自己的 $a_{j}$。

为了公平，刷卡人的实际净支出不能超过其个人消费额。也就是说，若选第 $p$ 个人，则须满足：总消费额减去其余所有人贡献的现金，不大于 $b_{p}$。请找出一个合适的买单人，或判断不存在。

输入格式

第一行包含 $n$（$2 \leq n \leq 100000$）。

接下来 $n$ 行，第 $j$ 行包含 $a_{j}$、$b_{j}$（$1 \leq a_{j}, b_{j} \leq 1000$），分别表示此人由别人买单时贡献的现金和此人的消费额。

输出格式

如果不存在合适的买单人，输出 impossible。否则输出一位合适买单人的编号 $p$（$1 \leq p \leq n$）。有多个合法答案时输出任意一个即可。

样例

3
4 3
5 4
1 3

3

5
1 4
8 1
1 4
2 5
4 6

impossible

8
4 3
5 8
7 2
1 9
6 3
2 6
5 7
8 6

4

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。