Joey loves to eat Pizza. But he is worried as the quality of pizza made by most of the restaurants is deteriorating. The last few pizzas ordered by him did not taste good :(. Joey is feeling extremely hungry and wants to eat pizza. But he is confused about the restaurant from where he should order. As always he asks Chandler for help.

Chandler suggests that Joey should give each restaurant some points, and then choose the restaurant having maximum points. If more than one restaurant has same points, Joey can choose the one with lexicographically smallest name.

Joey has assigned points to all the restaurants, but can't figure out which restaurant satisfies Chandler's criteria. Can you help him out?

 

Input:

First line has N, the total number of restaurants.

Next N lines contain Name of Restaurant and Points awarded by Joey, separated by a space. Restaurant name has no spaces, all lowercase letters and will not be more than 20 characters.

 

Output:

Print the name of the restaurant that Joey should choose.

 

Constraints:

1 <= N <= 10⁵

1 <= Points <= 10⁶

 

SAMPLE INPUT 3 Pizzeria 108 Dominos 145 Pizzapizza 49

 

SAMPLE OUTPUT Dominos

 

Explanation Dominos has maximum points.

 

Note: Use Java 7 programming lang..

 

Wrote code for above problem and pasted code below.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Restaurants
{

   public static void main(String args[])
   {
      Scanner in = new Scanner(System.in);
      
      int n = in.nextInt();
      in.nextLine();     // to consume next line
      if (n >=1 && n<= Math.pow(10,5)) {
         String line = in.nextLine();
         String[] parts = line.split(" ");
         List<Restaurant> restaurants = new ArrayList<Restaurant>();
         for (int i = 0; i < parts.length ; i = i+2) {
            Restaurant restaurant = new Restaurant();
            restaurant.setName(parts[i]);
            int points = Integer.parseInt(parts[i+1]);
            if ( points >=1 && points <=Math.pow(10, 6)) {
               restaurant.setPoints(points);  
            }
            restaurants.add(restaurant);            
         }
         
         // sorting restarants
         Collections.sort(restaurants);
         System.out.println(restaurants.get(restaurants.size() - 1).getName());
      } else {
         
      }
   }
   
   static class Restaurant implements Comparable<Restaurant>
   {
      private String name;
      private int points;

      public String getName()
      {
         return name;
      }

      public void setName(String name)
      {
         this.name = name;
      }

      public int getPoints()
      {
         return points;
      }

      public void setPoints(int points)
      {
         this.points = points;
      }

      // sorting based on points , if points are same then sorting based on name
      @Override
      public int compareTo(Restaurant o)
      {
         if (this.points < o.getPoints()) {
            return -1;
         } else if (this.points > o.getPoints()) {
            return 1;
         } else {
            return this.name.compareTo(o.name);
         }
      }

   }


}