//Alex Silva copyright (c) 2013 

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class puzzle2Driver {

    //DRIVER FIELDS
	private static Scanner scn;
	private static ArrayList<Song> arrInput;
	private static String[] tokens;
	private static String strIn;
	private static int nSongs;
	private static int nSelects;
	
	//MAIN METHOD
	public static void main(String[] args) throws IOException {
		
		scn = null;

        try {
            scn = new Scanner(System.in);
            
    		//accept first line of input
       		//split and parse entries; add to values to variables
            if(scn.hasNext()){
            	strIn = scn.nextLine();
        		tokens = strIn.split(" ");
        		nSongs = parseToInt(tokens[0].trim());
        		nSelects = parseToInt(tokens[1].trim()); 
        		arrInput = new ArrayList<Song>(nSongs);
            }
            
    		//accept and record first song info in input array
            if(scn.hasNext()){
	            strIn = scn.nextLine();
	    		tokens = strIn.split(" ");
	    		//add first song to array
	    		arrInput.add((new Song(parseToInt(tokens[0].trim()), tokens[1].trim(), 0)));
	    		//set quality value to 1
	    		arrInput.get(0).setnQuality(1.0);
	    		//if first song has 0 plays
	    		if(arrInput.get(0).getnPlayNum()==0){
	    			arrInput.get(0).setnPlayNum(1);
    			}
            }
            
            //if only one song is added
            if(nSongs==1){
            	System.out.println(arrInput.get(0).getSongName());
            }
            
            //otherwise, proceed:
            else{
            
	    		Song songIn;
	    		double tempQ;
	    		int i=1;
	            while (scn.hasNext()) {
	            	strIn = scn.nextLine();
	    			tokens = strIn.split(" ");
	    			//create and add song to array
	    			songIn = new Song(parseToInt(tokens[0].trim()), tokens[1].trim(), i+2);
	    			arrInput.add(songIn);
	    			//calculate quality using:
	    			//q(i) = song(i).plays / (song(0).plays / i )
	    			tempQ = (double)arrInput.get(i).getnPlayNum() / ((double)arrInput.get(0).getnPlayNum() / (double)(i+1));
	    			//set Quality value to current song
	    			arrInput.get(i).setnQuality(tempQ);
	    			i++;
	    			if(i==nSongs){
	    				break;
	    			}
	            }
	            
	    		//sort array of songs by quality value
	    		Collections.sort(arrInput);
	    		
	    		//prints only the number of songs defined earlier
	    		for (i = 0; i < nSelects; i++) {
	    			System.out.println(arrInput.get(i).getSongName());
	    		}
            }
        }
        
        catch(Exception e){
            System.out.println("Exception caught");
        	System.out.println(e.getStackTrace());

        } finally {
            if (scn != null) {
                scn.close();
            }
        }

	}
	
	//helper method for parsing from String to integer
	private static int parseToInt(String strIn) {
		int nRes = -1;
		try{
			nRes = Integer.parseInt(strIn.trim());
		}
		catch(NumberFormatException nfe){
			System.out.println("Error parsing to Integer");
		}
		return nRes;
	}
	
	//PRIVATE SONG UTILITY CLASS
	private static class Song implements Comparable<Song> {
		
		//Song Fields
		private int nPlayNum;
		private String songName;
		private int nTrackNum;
		private double nQuality;
		
		//Song constructor 
		public Song(int nPlayNum, String songName, int nTrackNum){
			this.nPlayNum = nPlayNum;
			this.songName = songName;
			this.nTrackNum = nTrackNum;
		}
		
		@Override
		public int compareTo(Song o) {
            
			if(getnQuality() > o.getnQuality()){
				return -1;
			}
			
			if(o.getnQuality() > getnQuality()){
				return 1;
			}
			
			//if quality values are equal, put songs with lower track numbers first 
			if(getnTrackNum() < o.getnTrackNum()){
				return -1;
			}
			
			return 1;
			
			//note: no way to return 0, since songs can't have the same track number
			
		}
		
		//GETTERS SETTERS
		public int getnPlayNum() {
			return nPlayNum;
		}
		
		public void setnPlayNum(int nPlays) {
			nPlayNum = nPlays;
		}
		
		public String getSongName() {
			return songName;
		}
		
		public double getnQuality() {
			return nQuality;
		}

		public void setnQuality(double nQuality) {
			this.nQuality = nQuality;
		}

		public int getnTrackNum() {
			return nTrackNum;
		}
	}
	/* comment */ 


}