Bohater [B]
Limit pamięci: 128 MB
Na półkach bajtockich supermarketów pojawiła się właśnie nowa gra komputerowa,
w której kierujemy poczynaniami dzielnego herosa Bitora, mającego za zadanie pokonać potworów zamieszkujących lochy Bajtogrodu.
Dla uproszczenia potwory będziemy numerować liczbami od do .
Podczas walki z potworem o numerze Bitor doznaje obrażeń, które kosztują go punktów życia.
Potwór ten broni skrzyni z eliksirem zdrowia, który po wygranej walce przywraca Bitorowi punktów życia.
Bitor pokonuje potwory bez trudu, jednak nie może dopuścić, by w dowolnym momencie liczba jego punktów życia spadła do zera (lub poniżej).
Czy Bitor może stawać do walki z przeciwnikami w takiej kolejności, by pokonać wszystkie potwory?
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite i (), oznaczające liczbę potworów i początkową liczbę punktów życia Bitora.
W kolejnych wierszach znajdują się opisy potworów: -ty z tych wierszy zawiera
dwie liczby całkowite i (), oznaczające obrażenia zadawane przez potwora o numerze oraz moc eliksiru, który można wypić po jego pokonaniu.
Wyjście
Pierwszy wiersz wyjścia powinien zawierać jedno słowo TAK lub NIE, w zależności od tego, czy Bitor jest w stanie pokonać wszystkie potwory.
Jeśli da się pokonać wszystkie potwory, należy wypisać także drugi wiersz zawierający ciąg parami różnych liczb całkowitych z zakresu od do , pooddzielanych pojedynczymi odstępami.
Ciąg ten powinien opisywać przykładową kolejność toczenia walk, a jego
kolejne wyrazy powinny odpowiadać numerom kolejno pokonywanych potworów.
Jeśli istnieje więcej niż jedna poprawna odpowiedź, Twój program powinien wypisać dowolną z nich.
Przykład
Dla danych wejściowych:
3 5
3 1
4 8
8 3
poprawną odpowiedzią jest:
TAK
2 3 1
Autor zadania: Przemysław Uznański.