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.