AtCoder 猜拳 2

题目描述

$N$ 名 AtCoder 用户聚在一起玩「AtCoder 猜拳 2」。第 $i$ 名用户的名字是 $S_i$,段位是 $C_i$。

「AtCoder 猜拳 2」按以下方式游玩:

按用户名的字典序从小到大,给用户分配编号 $0, 1, \dots, N - 1$。

设 $T$ 为这 $N$ 名用户的段位之和。被分配编号 $T \bmod N$ 的用户获胜。

输出获胜用户的名字。

什么是字典序?

字典序,简单来说,就是「单词在字典中出现的顺序」。更严谨地,两个由小写英文字母组成的相异字符串 $S$ 与 $T$ 的大小比较算法如下(这里将「$S$ 的第 $i$ 个字符」记作 $S_i$):

设 $L$ 为 $S$ 与 $T$ 中较短者的长度。对 $i = 1, 2, \dots, L$,依次检查 $S_i$ 与 $T_i$ 是否一致。

• 若存在 $i$ 使得 $S_i \neq T_i$,设 $j$ 为最小的这样的 $i$。比较 $S_j$ 与 $T_j$:若 $S_j$ 在字母表顺序上小于 $T_j$,则 $S \lt T$;否则 $S \gt T$。算法到此结束。
• 若不存在 $i$ 使得 $S_i \neq T_i$,则比较 $S$ 与 $T$ 的长度:若 $S$ 比 $T$ 短,则 $S \lt T$;若 $S$ 比 $T$ 长,则 $S \gt T$。算法到此结束。

输入格式

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

$N$
$S_1$ $C_1$
$S_2$ $C_2$
$\vdots$
$S_N$ $C_N$

输出格式

在一行内输出答案。

样例

3
takahashi 2
aoki 6
snuke 5

snuke

这 3 名用户的段位之和为 $13$。将名字按字典序排序得到 aoki、snuke、takahashi,因此 aoki 被分配编号 $0$,snuke 为 $1$,takahashi 为 $2$。

由于 $13 \bmod 3 = 1$,输出被分配编号 $1$ 的 snuke。

3
takahashi 2813
takahashixx 1086
takahashix 4229

takahashix

数据范围

• $1 \le N \le 100$
• $S_i$ 是由小写英文字母组成的字符串,长度在 $3$ 到 $16$ 之间(含端点)
• $S_1, S_2, \dots, S_N$ 互不相同
• $1 \le C_i \le 4229$
• $C_i$ 是整数