|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초 (추가 시간 없음)||256 MB||2||2||2||100.000%|
Maggy is a die hard -- she still has a grade book and collects hand written grades from her lecturers. The lecturers' offices are numbered with consecutive natural numbers, starting from $1$, and are located along an infinite corridor. The grade from each lecture can be picked up daily, but only in a specific office and only for one minute during the day. Receiving a grade takes a negligible amount of time, but moving between adjacent offices, in any direction, takes exactly $1$ minute. A single lecturer can read several different lectures and then they may, although does not have to, give the grades to some of them at the same time; in such a case, receiving any number of grades still takes negligible amount of time.
Maggy attended $n$ lectures and for each of them she knows in which office and in which minute of the day she can get the grade. Every day Maggy gets up early, so that in minute $1$ she can be in any office. Help her determine the minimum number of days she needs to collect all the grades.
The first line of the input contains one integer $n$ ($ 1 \leq n \leq 500\,000 $) denoting the number of lectures Maggy attended. In each of the next $n$ lines there is a description of one lecture. One description consists of two integers $ p, t $ ($ 1 \leq p, t \leq 10 ^ 9 $), separated by a single space, meaning that a grade from this lecture can be obtained daily in office $p$ in $t$-th minute counted from the beginning of each day.
You should write one integer number in the first and only line of the output -- the minimal number of days Maggy needs to pick up all grades.
7 2 1 1 4 3 2 1 1 4 2 5 3 1 1
On the first day Maggy can collect all grades from office number 1. On the second day she is able to collect grades in offices 2 and 3, and on the third day -- in offices 4 and 5.