Your 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 (x1, y1) you can go to any other (x2, y2) where x2 ≥ x1 and y2 ≥ y1.
Knowing the age of the salesman and the store each of them works, determine the maximum number of items you can buy.
The first line has an integer N, the number of salesmen.
Each of the next N lines has two integers each, xi and yi, meaning the ith salesman is in the store with coordinates (xi, yi).
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
Print a single integer, the maximum number of items you can buy.
2
1 1
1 2
2
2
2 1
1 1
1
3
1 1
1 2
2 1
2
4
1 1
1 2
2 1
2 2
3
| 2010 USP Try-outs |
|---|
| Finished |
