Wspinaczka [B]

Limit pamięci: 64 MB

Na zajęcia na ściance wspinaczkowej uczęszcza osób. Każda z osób ma własną, osobną trasę, po której może poruszać się w górę lub w dół. Wspinaczka odbywa się w parach. W każdej parze wspinają się osoby z dwóch sąsiednich tras, przywiązane do wspólnej liny. Każda lina jest zaczepiona u szczytu ścianki pomiędzy obiema trasami i powinna być cały czas napięta.

Wiadomo, że długość każdej z lin jest nie większa niż wysokość ścianki wspinaczkowej. Poza tym, kiedy jedna osoba z danej pary jest na szczycie ścianki, druga nie może już zejść niżej.

Rysunek: Wspinająca się para osób przywiązana do jednej liny.

Każda osoba na ściance ma po swojej lewej i prawej stronie po jednym sąsiedzie, oprócz dwóch skrajnych osób, które mają jednego sąsiada. Na koniec zajęć prowadzący chciałby, aby każda osoba ustawiła się na takiej wysokości, aby powstało jak najwięcej par sąsiednich osób z różnych lin, które będą w tej samej odległości od punktu zaczepienia swojej liny. Pomóż uczestnikom i oblicz maksymalną liczbę takich par osób.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę lin na ściance wspinaczkowej. W kolejnych wierszach opisane są pary osób przywiązanych do poszczególnych lin, w kolejności od lewej do prawej. W każdym wierszu znajdują się dwie liczby całkowite (), oznaczające odpowiednio odległość lewej i prawej osoby od punktu zaczepienia liny.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą maksymalnej liczbie par sąsiednich osób z różnych lin, które mogą ustawić się w takiej samej odległości od szczytu ścianki.

Przykład

Dla danych wejściowych:

3
1 1
3 2
1 4

poprawną odpowiedzią jest:

2

Autor zadania: Jacek Tomasiewicz.