Tygrysy
Limit pamięci: 32 MB
Bajtockie tygrysy to niezwykłe zwierzęta, a ich nietypowe zwyczaje od zawsze fascynowały zoologów i matematyków.
Ustalono niedawno, że dzielą się one na specyficzne gatunki.
Tygrysa nazwiemy -tygrysem, jeśli spotkawszy tygrysa mniejszego co najmniej razy
od siebie, zaatakuje go i zje, jednak nie odważy się tknąć żadnego większego tygrysa.
W bajtockim ZOO żyje tygrysów. Niestety miejsce w ZOO jest ograniczone,
dlatego też dyrektor stwierdził, że trzeba tak przydzielić zwierzęta do wybiegów,
aby zająć ich jak najmniej.
Oczywiście nie można przy tym dopuścić, by jakikolwiek tygrys został pożarty.
Dyrektor ma wyraźne problemy z zakwaterowaniem tygrysów, zwrócił się więc do Ciebie po pomoc.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
() - liczbę tygrysów w ZOO.
Każdy z kolejnych wierszy zawiera opis jednego tygrysa.
Opis taki składa się z dwóch liczb całkowitych oraz
(, ),
oddzielonych pojedynczym odstępem.
Oznaczają one, że -ty tygrys jest -tygrysem i ma rozmiar .
Możesz założyć, że w przynajmniej przypadków testowych występują jedynie -tygrysy.
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę całkowitą -
najmniejszą liczbę wybiegów, do których można bezpiecznie przydzielić tygrysy.
Przykład
Dla danych wejściowych:
5
8 3
10 2
15 2
18 2
28 3
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: W powyższym przykładzie tygrysy o rozmiarach , , mogą występować na wybiegu number ,
zaś tygrysy o rozmiarach , mogą zostać pokazane na wybiegu numer .
Autor zadania: Michał Włodarczyk.