gistfile1.java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static class Music {
        private final Double rating;
        private final String name;

        public Music(String name, double rating) {
            this.name = name;
            this.rating = rating;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s;
        Scanner scanner = new Scanner(System.in);

        int size = scanner.nextInt(), output_count = scanner.nextInt();

        PriorityQueue<Music> musics = new PriorityQueue<Music>(output_count, new Comparator<Music>() {
            @Override
            public int compare(Music music, Music music2) {
                return music.rating.compareTo(music2.rating);
            }
        });

        for(int i = 0; i < size; i++) {
            long count = scanner.nextLong();
            String name = scanner.nextLine().trim();

            Music music = new Music(name, count / (1.0 / (size + i)));
            if(musics.size() < output_count) {
                musics.add(music);
            }
            else if(musics.peek().rating < music.rating) {
                musics.poll();
                musics.add(music);
            }
        }

        Stack<Music> ordered = new Stack<Music>();
        while(musics.size() > 0) {
            ordered.push(musics.poll());
        }

        while(!ordered.empty()) {
            System.out.println(ordered.pop().name);
        }
    }
}