Bandżo [B]
Limit pamięci: 128 MB
Pewnego dnia Bajtazar udał się na rynek w Bajtogrodzie, aby zagrać na bandżo.
Żeby nie uprzykrzać zbytnio życia okolicznym mieszkańcom, postanowił, że zagra tylko dwie krótkie, jednominutowe piosenki.
Mimo tego, Bajtazar bardzo chciał, by usłyszało go jak najwięcej osób.
Zagrał więc jedną piosenkę, nieco odczekał, po czym zagrał drugą.
Teraz zastanawia się, czy przypadkiem jego występu nie mogło usłyszeć więcej osób.
W ciągu dnia przez rynek przewinęło się osób, które będziemy numerować od do .
Bajtazar dokładnie zapamiętał, kto i kiedy przyszedł na rynek.
Osoba numer pojawiła się na rynku dokładnie na początku -tej minuty (licząc od świtu)
i opuściła rynek na początku -tej minuty.
Bajtazar chciałby obliczyć, ile maksymalnie osób usłyszałoby jego granie,
gdyby rozpoczynał występy w optymalnych momentach.
Problem ten przerósł jednak jego umiejętności rachunkowe, gdyż dzień w Bajtocji trwa minut.
Zrozpaczony Bajtazar poprosił Cię o pomoc.
Zakładamy, że Bajtazar gra dokładnie dwa razy, za każdym razem po jednej minucie.
Każdy występ może się zacząć o dowolnej porze.
W szczególności druga piosenka może rozpocząć się od razu po zakończeniu pierwszej.
Dana osoba słyszy występ, jeśli znajduje się na rynku w trakcie całej minuty, podczas której Bajtazar gra.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita ()
oznaczająca liczbę osób, które przyszły na rynek w ciągu dnia.
Każdy z kolejnych wierszy opisuje jedną z osób.
W -tym z tych wierszy znajdują się dwie liczby całkowite oraz (), które
oznaczają, że osoba numer przyszła na rynek na początku minuty , a poszła na początku minuty .
Wyjście
Twój program powinien wypisać na wyjście maksymalną liczbę różnych osób, które mogą usłyszeć występy Bajtazara na bandżo.
Przykład
Dla danych wejściowych:
7
3 6
1 16
9 13
4 6
7 9
1 1
9 10
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu: Bajtazar rozpoczyna pierwszą piosenkę w dowolnym momencie czwartej
lub na początku piątej minuty.
Pierwszą piosenkę słyszą więc osoby , i .
Drugą piosenkę Bajtazar gra w dziewiątej minucie, gdy na rynku są osoby , i .
Łącznie Bajtazara słyszy różnych osób.
Autor zadania: Jakub Łącki.