andy6804tw
10/8/2017 - 11:19 AM

uva

import java.util.*;
public class Main {

	public static void main(String[] args) {
		
		Scanner scn=new Scanner(System.in);
		int t=Integer.parseInt(scn.nextLine());
		while(t--!=0) {
			String s[]=scn.nextLine().split(" ");
			int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]);
			LinkedList<Score> list = new LinkedList<Score>(); 
			for(int i=0;i<n;i++) {
				s=scn.nextLine().split(" ");
				list.offer(new Score(i+1,s[0],Integer.parseInt(s[1]),Integer.parseInt(s[1])));
			}
	        
	        for(int i=0;i<k;i++) {
	        		Collections.sort(list);
	        		Score temp=list.poll();
	        		String name=temp.name;
	        		int freq=temp.freq,origin=temp.origin,priority=temp.priority;
	        		System.out.println(freq+" "+name);
	        		list.offer(new Score(priority,name,freq+origin,origin));
	        }
		}
	}

}
class Score implements Comparable<Score> {
    int freq,origin,priority;
    String name;
 
    public Score(int priority,String name,int freq,int origin) {
    		this.priority=priority;
        this.freq = freq;
        this.name = name;
        this.origin=origin;
    }
 
    @Override
    public int compareTo(Score o) {
        return (freq < o.freq)||(freq == o.freq)&&(priority<o.priority) ? -1 : (freq > o.freq)||(freq== o.freq)&&(priority>o.priority) ? 1 : 0;
    }
}