Demonstracje

Limit pamięci: 128 MB

W najbliższą niedzielę w Bajtogrodzie będzie obchodzony doroczny Dzień Bajtu - jedno z najważniejszych bajtockich świąt. Wszystko wskazuje jednak na to, że tegoroczne obchody nie będą tylko sielskim rodzinnym festynem.

Otóż w ostatnim czasie obywatele Bajtogrodu są podzieleni w jednej zasadniczej kwestii. Jedni uważają, że zgodnie z tradycją bajt powinien być zawsze równy ośmiu bitom. Są jednak zwolennicy postępu, którzy chętniej widzieliby dużo pojemniejsze, 16-bitowe bajty. Inni patrzą na całą sprawę znacznie bardziej rygorystycznie i najchętniej ogłosiliby, że bajt powinien mieć zawsze tylko 4 bity. Są wreszcie w Bajtogrodzie mniej znaczące ruchy wywrotowe, których członkowie twierdzą, że liczba bitów w bajcie nie powinna być potęgą dwójki, a nawet że nie musi być w ogóle parzysta! Każde ze stowarzyszeń zaplanowało na niedzielę demonstrację, w trakcie której będzie próbowało przekonać mieszkańców Bajtogrodu do swojej racji.

Wielu obywateli miasta obawia się, że duża liczba demonstracji może zakłócić obchody Dnia Bajtu. Burmistrz Bajtogrodu wyczuł, że może zyskać duże poparcie społeczne, nie wyrażając zgody na przeprowadzenie niektórych demonstracji. Ponieważ taka decyzja zawsze budzi kontrowersje, burmistrz postanowił, że ograniczy się do odwołania co najwyżej dwóch demonstracji. Chciałby przy tym wybrać takie demonstracje, po których odwołaniu łączny czas, w trakcie którego będą odbywały się w mieście jakiekolwiek demonstracje, będzie możliwie najkrótszy. Pomóż burmistrzowi i podpowiedz mu, ile czasu bez demonstracji w mieście jest on w stanie w ten sposób uzyskać.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę zaplanowanych demonstracji. Każdy z kolejnych wierszy opisuje jedną demonstrację: -ty z tych wierszy zawiera dwie liczby całkowite oraz (), które oznaczają, że -ta demonstracja rozpoczyna się bajtominut po wschodzie słońca i kończy się bajtominut po wschodzie słońca.

Wyjście

Twój program powinien wypisać dokładnie jedną nieujemną liczbę całkowitą, oznaczającą, o ile maksymalnie może skrócić się czas, podczas którego odbywać się będą demonstracje, jeśli burmistrz Bajtogrodu odwoła co najwyżej dwie demonstracje.

Przykład

Dla danych wejściowych:

5
0 9
1 4
2 5
7 9
6 7

poprawną odpowiedzią jest:

4

Wyjaśnienie do przykładu: Burmistrz Bajtogrodu powinien nie wydać pozwoleń na pierwszą oraz na czwartą demonstrację.

Autor zadania: Jakub Łącki.