Building Blocks

Interview

Time limit1sMemory limit1024 MB

Summary

Given blocks that may be rotated, find the height of the tallest tower where each block fits within the width and length of the block below.

Level: Medium4 of 10
Topics: Sorting, Dynamic programming
Solved: No attempts yet

Problem

The cows want to build a tower out of the blocks they found. Given the sizes of the blocks, determine the height of the tallest stable tower that can be built. Each block is one unit high and has a width and a length. The blocks must be stacked with all their edges parallel to the axes, and each block may be rotated 90 degrees. In a stable tower, each higher block must be no larger than the block on which it sits: both its width and its length must be no larger than the width and length of the block below it.

Input

The first line contains one integer $B$ , where $1 \le B \le 100$ , the number of blocks. Each of the next $B$ lines contains two integers, the width and length of a square block. Each dimension is at least 1 and at most 100.

Output

Print a single line with one integer, the height of the tallest stable tower that can be built.

Examples1

Example 1
Input
```
5
3 7
4 5
4 5
5 6
2 2
```
Expected output
```
4
```