B - 町の合併
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
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