Akib is a very good student but his reading table is very messy. One Friday afternoon, Akib is sitting idle and relaxing. To make his leisure time effective, he decides to clean his table.
First, Akib wants to sort his books and make a stack of them. He calls a stack of books perfect stack if a book's length and width is strictly less than the previous book.
For better explanation let's consider a stack of books A = {b1, b2, b3, ......, bm}. A is said to be a perfect stack if length and width of i-th book is strictly less than the length and width of the (i-1)-th book. The size of a perfect stack is the total number of books in a perfect stack.
Akib has n books. He also knows the value of two sides of each book (i.e. width and height of each book). In the process of making a perfect stack it is allowed to rotate a book 90 degrees. If you rotate a book 90 degrees then it's width becomes length and length becomes width.
Now Akib wants to make a perfect stack of books, the size of which is as big as possible from the n books he has. Help Akib to solve this task.
Input
The first line contains an integer n (1 ≤ n ≤ 5000) — the number of books Akib has. Then there will be n lines, each of them contains two integer numbers, Ai and Bi — the length of two sides of the i-th book (1 ≤ Ai, Bi ≤ 100).
Output
Print an integer which is the maximum perfect stack size.
Samples
| Input | Output |
|---|---|
4 7 7 10 13 14 9 8 13 | 3 |
It is possible to make a perfect stack of maximum size 3. First Akib choose the 3rd book, then 4th book then the 1st book. | |
| Input | Output |
|---|---|
2 15 15 15 15 | 1 |
Akib can make a perfect stack of a maximum size of 1 by choosing the 1st book or the 2nd book. | |
