Weird Multiplayer Scoring

0

0 votes
Problem

As the students are back in hostel after a long time, the gamers have decided to have a LAN gaming competition to find out who has utilized his time in gaming during vacations. They play "Counter ATOD". However, the scoring of this game is weird. There are N players and there are M rounds. Initially, each player has 0 points. The player gets the points only if he has won the round. Points can be negative too(weird).

The winner of the whole contest is the one who has maximum points after any round. However, it isn't necessary at all that the winner will have maximum points at the end of the game. As the scoring is pretty weird, they asks for your help.

Input Format :
First line of input will consist of N and M denoting the number of players and rounds respectively.
Next M lines will contain the name of the player who won the round and the points P he earned after that round. First round will always have positive points.

Output Format: The only line of output will contain the name of the winner who got maximum points in the contest at any point of the game. In case of draw, the winner will be the player who got maximum points earlier.

Constraints :
1 ≤ N ≤ 100
1 ≤ M ≤ 5000
1 ≤ Length of name ≤ 15
-106 ≤ P ≤ 106

Problem Setter : Swastik Mundra

Sample Input
3 5
Murliwala 5
Mithaiwala 4
Mithaiwala 4
Mithaiwala -2
Mirchiwala 8
Sample Output
Mithaiwala
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

After round 1, Murliwala wins the round and gains 5 points but as Mirchiwala and Mithaiwala has not won the round, they will not gain any point.

After round 2, Mithaiwala wins the round and gains 4 points. However Murliwala has still 5 points and Mirchiwala has 0 points.

After round 3, Mithaiwala wins the round and gains 4 points. His total is 8 points now and is maximum. However Murliwala has still 5 points and Mirchiwala has 0 points.

After round 4, Mithaiwala wins again and gains -2 points which brings his total to 6 points.

After round 5, Mirchiwala wins and gains 8 points.

Maximum points throughout the game was 8 but as Murliwala earned 8 points first he is the winner. However, the total of Mithaiwala at the end was 6.

Editor Image

?