AtCoder Beginner Contest 033

B - 町の合併


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

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

Submit提出する