Most Popular Category

You are given a list of transactions, each in the format Category:Amount. Your task is to determine the category with the highest total sales value. In case of a tie (i.e. when two or more categories have the same total sales), you must return the category which is alphabetically smallest.

Mathematically, let ( S(c) ) be the total sales for category ( c ). Then you need to find a category ( c^* ) such that

[ S(c^) = \max_{c \in C} S(c) \quad \text{and if } S(c_1) = S(c_2) \text{ then } c^ = \min{c_1, c_2} ]

Note: The input transactions are given one per line. Ensure correct parsing and handling of input.

inputFormat

The first line of input contains a single integer ( n ) (( 1 \le n \le 10^5 )) that denotes the number of transactions. Each of the following ( n ) lines contains a transaction in the format 'Category:Amount', where Category is a non-empty string (without spaces) and Amount is a positive integer.

outputFormat

Output a single line containing the category with the highest total sales value. In the case of a tie, output the one which comes first in alphabetical order.## sample

5
Electronics:200
Clothing:100
Electronics:150
Groceries:300
Clothing:200

Electronics