Obwarzanki
Limit pamięci: 32 MB
Witek wybrał się na jarmark.
W mgnieniu oka zlokalizował stoisko z najlepszymi obwarzankami.
Nie zastanawiając się długo kupił jedną porcję obwarzanków.
Warto wiedzieć, że Bajtockie obwarzanki są zawsze nawlekane na patyk,
a nie na kółko, jak na większości naszych jarmarków.
Obwarzanki można zdejmować z lewego bądź prawego końca patyka.
Każdego obwarzanka charakteryzują dwie wartości: średnica zewnętrzna (Z)
i średnica wewnętrzna (W).
Jest to przedstawione na rysunku.
Gdy chcemy wyjąć pewien obwarzanek znajdujący się pomiędzy innymi obwarzankami, to
możemy spróbować przełożyć jednego obwarzanka przez drugiego.
Uda nam się to tylko wtedy, gdy średnica wewnętrzna któregoś z tych dwóch obwarzanków
jest większa bądź równa od średnicy zewnętrznej drugiego z nich.
W przeciwnym wypadku musimy najpierw zdjąć obwarzanka z lewej bądź prawej strony.
Witkowi spodobał się pewien obwarzanek i zastanawia się,
ile minimalnie innych obwarzanków będzie
musiał zdjąć, zanim dostanie się do swojego wybranego.
Wejście
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite ,
(), oznaczające odpowiednio liczbę obwarzanków znajdujących się
na patyku oraz numer obwarzanka (licząc od lewej strony), którego wybrał Witek.
W następnych wierszach znajdują się opisy kolejnych obwarzanków nawleczonych na patyk,
począwszy od lewej strony.
Każdy z tych wierszy zawiera dwie liczby całkowite oraz
() oddzielone pojedynczym odstępem, oznaczające
odpowiednio średnicę wewnętrzną oraz średnicę zewnętrzną -tego obwarzanka.
Możesz założyć, że w testach wartych co najmniej punktów zachodzi dodatkowy warunek: .
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą
równą minimalnej liczbie dodatkowych obwarzanków, jakie powinien zdjąć Witek, aby dostać się
do wybranego.
W wyniku nie należy uwzględniać obwarzanka wybranego przez Witka.
Przykład
Dla danych wejściowych:
5 3
5 8
2 4
4 6
1 5
1 2
poprawną odpowiedzią jest:
1
Autor zadania: Jacek Tomasiewicz.