1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.io.BufferedInputStream;
import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeSet;

public class boh {
	
	public static void main(String[] args) {

		Scanner odczyt = new Scanner(new BufferedInputStream(System.in));
		int iloscPotworow = odczyt.nextInt();
		int iloscZycia = odczyt.nextInt();
		TreeSet<Przeciwnik> listaPrzeciwnikowPoDmgMaWiecejApteczki = new TreeSet<Przeciwnik>(new PoDmg());
		TreeSet<Przeciwnik> listaPrzeciwnikowPoDmgRowneDA = new TreeSet<Przeciwnik>(new PoDmg());
		TreeSet<Przeciwnik> listaPrzeciwnikowPoApteczceMaWiecejDmg = new TreeSet<Przeciwnik>(new PoApteczce());
		for (int i = 1; i <= iloscPotworow; i++) {
			int zadanyDmg = odczyt.nextInt();
			int apteczka = odczyt.nextInt();
			Przeciwnik przeciwnik = new Przeciwnik(i, zadanyDmg, apteczka);
			if (przeciwnik.apteczka > przeciwnik.zadaneDmg)
				listaPrzeciwnikowPoDmgMaWiecejApteczki.add(przeciwnik);
			else if (przeciwnik.apteczka == przeciwnik.zadaneDmg)
				listaPrzeciwnikowPoDmgRowneDA.add(przeciwnik);
			else
				listaPrzeciwnikowPoApteczceMaWiecejDmg.add(przeciwnik);
				
		}
		odczyt.close();
		
		int mierzenieZycia = iloscZycia;
		for (Przeciwnik p : listaPrzeciwnikowPoDmgMaWiecejApteczki) {
			mierzenieZycia -= p.zadaneDmg;
			if (mierzenieZycia <= 0)
				break;
			mierzenieZycia += p.apteczka;
		}
		if (mierzenieZycia <= 0){
			System.out.println("NIE");
			return;
		}
		
		for (Przeciwnik p : listaPrzeciwnikowPoDmgRowneDA) {
			mierzenieZycia -= p.zadaneDmg;
			if (mierzenieZycia <= 0)
				break;
			mierzenieZycia += p.apteczka;
		}
		if (mierzenieZycia <= 0){
			System.out.println("NIE");
			return;
		}		
		
		for (Przeciwnik p : listaPrzeciwnikowPoApteczceMaWiecejDmg) {
			mierzenieZycia -= p.zadaneDmg;
			if (mierzenieZycia <= 0)
				break;
			mierzenieZycia += p.apteczka;
		}
		if (mierzenieZycia <= 0){
			System.out.println("NIE");
			return;
		}
		else{
			System.out.println("TAK");
			for (Przeciwnik p : listaPrzeciwnikowPoDmgMaWiecejApteczki) {
				System.out.print(p.id + " ");
			}
			for (Przeciwnik p : listaPrzeciwnikowPoDmgRowneDA) {
				System.out.print(p.id + " ");
			}
			for (Przeciwnik p : listaPrzeciwnikowPoApteczceMaWiecejDmg) {
				System.out.print(p.id + " ");
			}
		}
	}

}

class PoApteczce implements Comparator<Przeciwnik> {
	@Override
	public int compare(Przeciwnik p, Przeciwnik d) {
		if (p.apteczka > d.apteczka)
			return -1;
		else if (p.apteczka < d.apteczka)
			return 1;
		else {
			if (p.zadaneDmg < d.zadaneDmg)
				return -1;
			else if (p.zadaneDmg > d.zadaneDmg)
				return 1;
			return 1;
		}

	}
}

class PoDmg implements Comparator<Przeciwnik> {
	@Override
	public int compare(Przeciwnik p, Przeciwnik d) {
		if (p.zadaneDmg < d.zadaneDmg)
			return -1;
		else if (p.zadaneDmg > d.zadaneDmg)
			return 1;
		else {
			if (p.apteczka > d.apteczka)
				return -1;
			else if (p.apteczka < d.apteczka)
				return 1;
			return 1;
		}

	}
}

class Przeciwnik {
	int id;
	int zadaneDmg;
	int apteczka;

	Przeciwnik(int id, int zadanyDmg, int apteczka) {
		this.id = id;
		this.zadaneDmg = zadanyDmg;
		this.apteczka = apteczka;
	}

}