시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

W sieci LinkNet komputery są przyłączone do linii komunikacyjnej w sposób przedstawiony na rysunku. Dostępne punkty przyłączeń są ponumerowane kolejno 0, 1, ..., R. Do jednego punktu może być przyłączony tylko jeden komputer. Każdy z komputerów może być przyłączony do sieci tylko w jednym punkcie. Komunikacja w sieci jest synchroniczna.

W danym takcie komputery przyłączone do punktów 0 ≤ a < bR mogą dokonać transmisji danych tylko wtedy, gdy żaden komputer przyłączony do łącza o numerze c, a < c < b nie bierze udziału w transmisji danych z jakimkolwiek innym komputerem. W jednym takcie komputer może brać udział tylko w jednej tranmisji.

Napisz program który:

  • wczytuje opisy transmisji, które trzeba zrealizować,
  • oblicza jaka jest minimalna liczba taktów wystarczających do zrealizowania transmisji,
  • wypisuje obliczoną liczbę.

입력

W pierwszym wierszu danych podana jest liczba transmisji N: 0 ≤ N ≤ 100000. W kolejnych N wierszach podane są opisy transmisji - po jednym w wierszu. Opis każdej transmisji składa się z dwóch liczb a, b: 0 ≤ a < b ≤ 1 000 000 000, oznaczających numery punktów, pomiędzy którymi ma być transmisja danych. Liczby a i b są oddzielone spacją.

출력

W pierwszym i jedynym wierszu wyniku powinna być podana jedna liczba: minimalna liczba taktów wystarczających do zrealizowania wszystkich transmisji opisanych w danych.

예제 입력 1

4
10 20
3 10
5 35
20 50

예제 출력 1

3