8588번 - Obwarzanki 다국어

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.

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite $n$, $m$ ($1 ≤ m ≤ n ≤ 1\,000\,000$), oznaczające odpowiednio liczbę obwarzanków znajdujących się na patyku oraz numer obwarzanka (licząc od lewej strony), którego wybrał Witek.

W $n$ 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 $w_i$ oraz $z_i$ ($1 ≤ w_i < z_i ≤ 1\,000\,000\,000$) oddzielone pojedynczym odstępem, oznaczające odpowiednio średnicę wewnętrzną oraz średnicę zewnętrzną $i$-tego obwarzanka.

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.