← 返回题目列表

AtCoder · abc033_b

B. 城镇合并

中文机器翻译题面 查看原题

問題文

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