Jest rok 21XX. Programowanie sportowe jest powszechnie uznawane za sport umysłowy i często pojawia się w telewizji, gazetach oraz innych mediach.

Jesteś dziennikarzem gazety JOI i zajmujesz się artykułami o programowaniu sportowym.

Wczoraj odbyły się międzynarodowe zawody w programowaniu sportowym z udziałem $N$ zawodników. Aby napisać o nich artykuł, otrzymałeś następujące informacje.

• Podobnie jak w Międzynarodowej Olimpiadzie Informatycznej, w zawodach uczestniczyli zawodnicy z różnych krajów. Kraje mają numery od $1$ do $N$. Z jednego kraju mogło przyjechać kilku zawodników. Niektóre kraje mogły też nie mieć żadnego reprezentanta.
• Zawody trwały 5 godzin.
• Liczba punktów zdobytych przez zawodnika podczas zawodów nigdy później nie malała.
• Po 2 godzinach od rozpoczęcia zawodów żaden z zawodników nie miał tyle samo punktów co inny. W ówczesnym rankingu zawodnik na miejscu $i$ ($1 \le i \le N$) pochodził z kraju $A_i$ i miał $B_i$ punktów.
• Na koniec zawodów żaden z zawodników nie miał tyle samo punktów co inny. W końcowym rankingu zawodnik na miejscu $i$ ($1 \le i \le N$) pochodził z kraju $C_i$ i miał $D_i$ punktów.

Jednak gdy przystąpiłeś do pisania artykułu, okazało się, że wyświetlanie krajów pochodzenia w rankingach działało nieprawidłowo. Informacje o krajach pochodzenia zawodników mogły być błędne. Wiadomo natomiast, że wyświetlone wyniki punktowe były poprawne.

Postanowiłeś więc wprowadzić jak najmniej zmian w otrzymanych informacjach, aby odtworzyć spójne rankingi: kraj pochodzenia tego samego zawodnika nie może zmieniać się w trakcie zawodów, a jego liczba punktów nie może maleć. Innymi słowy, chcesz zmienić jak najmniej spośród $2N$ wartości $A_1,\ldots,A_N,C_1,\ldots,C_N$, tak aby spełniony był następujący warunek:

• Istnieje permutacja $x_1,x_2,\ldots,x_N$ liczb $1,2,\ldots,N$ taka, że dla każdego $i=1,2,\ldots,N$ zachodzi $A_i=C_{x_i}$ oraz $B_i \le D_{x_i}$.

Ile co najmniej zmian trzeba wprowadzić w otrzymanych informacjach?

Zadanie

Dane są liczba uczestników zawodów oraz informacje o rankingach po 2 godzinach od rozpoczęcia i na koniec zawodów. Napisz program wyznaczający najmniejszą liczbę zmian informacji o krajach pochodzenia potrzebną do uzyskania spójnych rankingów.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczbę całkowitą $N$. Oznacza ona, że w zawodach uczestniczyło $N$ zawodników.
• Wiersz $i$ ($1 \le i \le N$) spośród kolejnych $N$ wierszy zawiera liczby całkowite $A_i,B_i$ oddzielone spacją. Oznacza to, że po 2 godzinach od rozpoczęcia zawodów zawodnik na miejscu $i$ był wyświetlany jako pochodzący z kraju $A_i$ i miał $B_i$ punktów.
• Wiersz $i$ ($1 \le i \le N$) spośród kolejnych $N$ wierszy zawiera liczby całkowite $C_i,D_i$ oddzielone spacją. Oznacza to, że na koniec zawodów zawodnik na miejscu $i$ był wyświetlany jako pochodzący z kraju $C_i$ i miał $D_i$ punktów.

Wyjście

Wypisz na standardowe wyjście w jednym wierszu najmniejszą liczbę zmian informacji o krajach pochodzenia potrzebną do uzyskania spójnych rankingów.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $2 \le N \le 200\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N$).
• $0 \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $B_i>B_{i+1}$ ($1 \le i \le N-1$).
• $1 \le C_i \le N$ ($1 \le i \le N$).
• $0 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $D_i>D_{i+1}$ ($1 \le i \le N-1$).
• Zmieniając niektóre wartości $A_1,\ldots,A_N,C_1,\ldots,C_N$, można uzyskać spójne rankingi.

Podzadania

Podzadanie 1 [15 punktów]

• $N \le 16$.

Podzadanie 2 [15 punktów]

• $N \le 50$.

Podzadanie 3 [30 punktów]

• $N \le 5000$.

Podzadanie 4 [40 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3
3 500
2 200
1 100
1 1000
3 700
3 400

Wyjście 1

1

Uwagi

Po zmianie $C_3$ na $2$ otrzymujemy następujące spójne rankingi:

• Zawodnik z kraju $3$, który po 2 godzinach był pierwszy z wynikiem $500$ punktów, na koniec zawodów był drugi z wynikiem $700$ punktów.
• Zawodnik z kraju $2$, który po 2 godzinach był drugi z wynikiem $200$ punktów, na koniec zawodów był trzeci z wynikiem $400$ punktów.
• Zawodnik z kraju $1$, który po 2 godzinach był trzeci z wynikiem $100$ punktów, na koniec zawodów był pierwszy z wynikiem $1000$ punktów.

Gdyby zamiast tego zmienić $C_2$ na $2$, rankingi byłyby niespójne: zawodnik z kraju $3$ miałby na koniec zawodów $400$ punktów, mimo że po 2 godzinach miał już $500$ punktów.

Nie można uzyskać spójnych rankingów, wprowadzając mniej niż jedną zmianę, więc wypisujemy $1$.

Wejście 2

3
3 3
3 2
1 1
3 4
3 2
1 1

Wyjście 2

0

Uwagi

W tym przypadku rankingi są spójne bez zmieniania informacji o krajach pochodzenia. Zauważ, że niektórzy zawodnicy mogli nie zwiększyć liczby punktów od chwili, gdy upłynęły 2 godziny od rozpoczęcia zawodów. Zauważ również, że w rankingu może być kilku zawodników z tego samego kraju.

Wejście 3

6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10

Wyjście 3

3

Uwagi

W tym przykładzie zmiana $A_1$ na $2$, $A_6$ na $4$ oraz $C_1$ na $4$ daje spójne rankingi.