Satelity

Limit pamięci: 64 MB

Bajtlandia przeżywa kolejny kryzys. Władzę przejęło wojsko. Aby zakończyć wojnę domową, dowódcy muszą już tylko znaleźć i wyeliminować pozostałości tych, którym nie spodobał się nowy układ sił. Nie jest to jednak takie proste... Dzięki (mniej lub bardziej dobrowolnym) raportom informatorów udało się ustalić listę potencjalnych miejsc, w których może znajdować się baza buntowników. Jako, że długotrwałe poszukiwania prowadzone w tych punktach nie przyniosły żadnych rezultatów, postanowiono podejść do problemu trochę inaczej - poczekać, aż przeciwnicy sami się ujawnią. Aby przedwcześnie nie wzbudzić ich podejrzeń, obserwacja będzie prowadzona za pomocą sieci satelitów szpiegowskich. Bajtlandię można sobie wyobrażać jako dwuwymiarowy krajobraz powstały przez połączenie punktów o różnych współrzędnych :

Satelity szpiegowskie można umieszczać tylko na prostej . Każdy taki satelita obserwuje te punkty, z którymi można go połączyć za pomocą odcinka, który nie przecina krzywej opisującej krajobraz (dotykania nie traktujemy jako przecinania). Twoim zadaniem jest obliczenie minimalnej liczby takich satelitów wystarczającej do jednoczesnej obserwacji wszystkich miejsc, w których podejrzewa się istnienie bazy rebeliantów.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i (, ) oddzielone pojedynczymi odstępami. Każdy z następnych wierszy zawiera opis krajobrazu Bajtlandii. W każdym z nich znajdują się trzy liczby całkowite , i (, , ) oddzielone pojedynczym odstępem; (, ) określa współrzędne punktu, a oznacza, że mogą w nim mieć swoją siedzibę buntownicy, a w przeciwnym wypadku. Możesz założyć, że oraz będą zawsze równe 0, a punkty będą podawane w kolejności ściśle rosnącej współrzędnej .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinna zostać wypisana jedna liczba całkowita - minimalna liczba potrzebnych satelitów.

Przykład

Dla danych wejściowych:

9 30
0 0 1
15 5 1
25 20 1
40 10 1
60 5 1
70 15 1
82 0 1
90 8 1
100 0 1

poprawną odpowiedzią jest:

2

Wyjaśnienie

Wystarczą satelity w oraz .

Autor zadania: Bartosz Górski (zapożyczenie).