Hide

Problem C
Coupons

Johan lives in Stockholm, which means he has to travel a lot by bus and subway. To travel, he needs to pay a number of coupons, depending on which zones his trip goes between.

A ticket is specified by an interval $[A, B]$ of zones it is valid in, and costs $2 + |A - B|$ coupons to purchase. When Johan buys a ticket, it is valid for exactly $10\, 000$ seconds and can be used for any trip which both starts and ends in zones in the interval $[A, B]$.

Johan is now going to make $N$ trips in order. For each trip, you will be given the zone Johan travels to, as well as the time at which he starts his trip. Initially, Johan is located in zone $0$. Help him minimize the number of coupons he must purchase!

Notes: Johan can buy a new ticket at any point, even if he already has a valid ticket. A ticket only needs to be valid at the moment Johan starts a trip, it is OK if the $10\, 000$ seconds expire while Johan is taking the trip.

Input

The first line contains the integer $0 \le N \le 400\, 000$ – the number of trips Johan wants to make.

The next $N$ lines contains two space-separated integers $0 \le Z \le 10$ and $0 \le T \le 10^9$, the zone and time for Johan’s next trip (in seconds from now). The values of $T$ will be strictly increasing.

Output

The first and only line should contain a single integer: the minimum number of coupons Johan must purchase to make all his trips.

Sample Input 1 Sample Output 1
2
1 4
2 5
4
Sample Input 2 Sample Output 2
2
1 4
2 10005
6
Sample Input 3 Sample Output 3
3
1 4
2 10
0 15
4
Sample Input 4 Sample Output 4
2
1 4
2 10004
4

Please log in to submit a solution to this problem

Log in