/******************************************************************* 
 Reference solution for Spring 2013 COS 126 Programming Exam 1
 Foodlympics Part Two: Gourmet Glory

 Author:       COS 126 Staff
 Netid:        cos126
 Precepts:     lots of them
 Dependencies: StdIn, StdOut
 Usage:        java FoodPart2 N
 
 Description:  Reads in names and scores for C countries. Prints out the N
               top-score countries in order. 
   
**************************************************************************/

public class FoodPart2 {

    // find the highest value in scores. set this value to 0, and 
    // return the corresponding element of countries.
    public static String best(String[] countries, int[] scores) {
        // number of countries
        int C = countries.length;

        // bestIndex is the index of the (earliest) max-score country
        int bestIndex = -1; 
        
        // max is the maximum score seen so far
        int max = Integer.MIN_VALUE;
        
        // find index of max-score country
        for (int i = 0; i < C; i++) {
            if (scores[i] > max) {
                max = scores[i];
                bestIndex = i;
            }
        }
        
        // do required update and return the winner
        scores[bestIndex] = 0;
        return countries[bestIndex];
    }

    // read in a file of scores, and take N from the command-line.
    // then print out the top N ranking countries from best to worst.
    public static void main(String[] args) {

        int C = StdIn.readInt();           // number of countries
        int N = Integer.parseInt(args[0]); // how many to rank

        String[] countries = new String[C];
        int[] scores = new int[C];

        // read the rest of the input
        for (int i = 0; i < C; i++) {
            countries[i] = StdIn.readString();
            scores[i] = StdIn.readInt();
        }
        
        // now print the results
        for (int i = 0; i < N; i++) {
            String nextRanked = best(countries, scores);
            StdOut.println("Rank " + (i+1) + ": " + nextRanked);
        }
    }
}