Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

D. Cairo Market

time limit per test

2 secondsmemory limit per test

64 MBinput

standard inputoutput

standard outputYour team is already making plans to visit Egypt. One of the places you want to meet is the famous Cairo Market. To save time, you decided you will get in through the door in the southwest of the market and get out through the northeast door. Besides, you will always walk toward the exit, that is, only north or east.

The Egyptian salesmen have a very peculiar rule: If you buy something from one of them, you can only buy again from another salesman that is older. The punishment for disrespecting this rule is loosing a hand. Of course this would harm your performance in the ICPC finals, and, for this reason, you will follow the local tradition. As it is not elegant to give the same kind of souvenir to your friends, so you decided that you will only buy at most one gift from each salesman.

The market is very organized. The places where the stores are all have the same width and height. Each place is identified by a coordinate (*x*, *y*) that indicates the column and the line that store is. When you are in a store, you can go to any store strictly north and/or east, that is, from (*x* _{1}, *y* _{1}) you can go to any other (*x* _{2}, *y* _{2}) where *x* _{2} ≥ *x* _{1} and *y* _{2} ≥ *y* _{1}.

Knowing the age of the salesman and the store each of them works, determine the maximum number of items you can buy.

Input

The first line has an integer *N*, the number of salesmen.

Each of the next *N* lines has two integers each, *x* _{ i} and *y* _{ i}, meaning the *i*th salesman is in the store with coordinates (*x* _{ i}, *y* _{ i}).

The salesmen are listed in ascending order of age, that is, from the youngest to the oldest. Two salesman can share the same store, in this case you can negotiate (or not) with each of them in any order. All salesmen are guaranteed to be within the market.

Limits

- 1 ≤
*N*≤ 10^{5} - 1 ≤
*x*_{ i},*y*_{ i}≤ 10^{3}

Output

Print a single integer, the maximum number of items you can buy.

Examples

Input

2

1 1

1 2

Output

2

Input

2

2 1

1 1

Output

1

Input

3

1 1

1 2

2 1

Output

2

Input

4

1 1

1 2

2 1

2 2

Output

3

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 08:18:04 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|