問題文
N 城镇合并,1 将有两个新城市。合并前 i (1 ≦ i ≦ N) 城镇的名称是 S_i 人口是 P_i 人。 我们正在尝试为一个新城市确定一个名称,如下。
- N 如果存在一个城镇,其人口超过每个城镇总人口的一半,则新城市的名称将继承该城镇的名称。
- 如果不存在这样的城镇,则新城市的名称为
atcoder。
由于给出了每个城镇的名称和人口,请输出合并后新城市的名称。
入力
输入将以以下格式从标准输入给出。
N S_1 P_1 S_2 P_2 : S_N P_N
- 1 行包含一个整数 N (2 ≦ N ≦ 1,000) 给出。
- 2 在 N 行提供有关每个城镇的信息。其中 i 行的长度仅由小写字母组成。 1 以上 20 以下字符串 S_i 和整数 P_i (1 ≦ P_i ≦ 100,000) 用空格分隔。
- S_1, S_2, …, S_N 都是不同的。
出力
合并后新城市名称 1 行输出。
还在输出末尾添加换行符。
入力例 1
4 unagi 20 usagi 13 snuke 42 smeke 7
出力例 1
snuke
4 城镇总人口为 20 + 13 + 42 + 7 = 82 人。 第3 个城镇的人口超过这个数量的一半。
入力例 2
5 a 10 b 20 c 30 d 40 e 100
出力例 2
atcoder
5 城镇总人口为 10 + 20 + 30 + 40 + 100 = 200 人,但没有一个城镇人口超过一半,所以
城市名称将为 atcoder 。
此外,
请注意,第 5 个城镇恰好拥有总人口的一半,但不是大多数。
有
入力例 3
14 yasuzuka 3340 uragawara 4032 oshima 2249 maki 2614 kakizaki 11484 ogata 10401 kubiki 9746 yoshikawa 5142 joetsu 100000 nakago 4733 itakura 7517 kiyosato 3152 sanwa 6190 nadachi 3169
出力例 3
joetsu