logo AlgoBeat OnlineJudge
登录 注册

#215300. [NWERC 2025] Fair Share

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

你们大学的队伍正在庆祝今年在卡尔斯鲁厄举行的 NWERC 中的出色表现。在当地一家餐厅享用美味晚餐后,你们结束了当天的活动。明天的回家之旅将会很漫长。

当试图支付账单时,你们小组意识到这家餐厅不收现金。此外,现在拆分账单为时已晚。措手不及之下,每个人都开始打开钱包,把一些现金放在桌上。必须有人用信用卡支付最终账单并收取现金。

每个人 在晚上消费了 ,但拥有 现金可用于贡献给小组支付(如果由他人支付)。为了保持公平,小组不希望支付最终账单(并从现金池中收取钱款)的人最终支付超过其个人份额。因此,如果由第 个人支付,那么在计入其他人的现金贡献后,账单的剩余部分不应超过其自身的账单份额

帮助小组确定应该由谁支付最终账单。

输入格式

输入包含:

  • 一行,一个整数 (),表示你们晚餐小组的人数。
  • 行,第 行包含两个整数 (),分别表示如果由他人支付,第 个人愿意贡献的现金金额,以及其账单份额。

输出格式

如果没有合适的人来结账,输出 impossible。否则,输出一个整数 (),表示结账的人的编号。 如果有多个有效解,你可以输出其中任意一个。

样例

样例输入 1

3
4 3
5 4
1 3

样例输出 1

3

样例输入 2

5
1 4
8 1
1 4
2 5
4 6

样例输出 2

impossible

样例输入 3

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

样例输出 3

4

数据范围与提示

样例 #2 解释。总账单为 。如果第一个人结账,他们会从其他人那里得到 现金, 自己支付 ,这超过了他们 的个人份额。类似地推理 其他每个人也会支付超过他们的个人份额, 因此,没有合适的人来结账。