The Bale Tower

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 20 bales with distinct widths and breadths, find the longest chain where each bale is strictly smaller than the one below it.

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

Problem

The cows have invented a new game. One cow brings out a set of $N$ ( $3 \le N \le 20$ ) hay bales from the shed. Every bale is exactly one unit tall, and each bale has its own distinct width and distinct breadth.

A second cow stacks some of the bales into a tower. A bale may rest on another bale only if the bale below has a strictly larger width and a strictly larger breadth than the bale on top. Bales may not be rotated, so width and breadth can never be swapped.

Determine the height of the tallest tower the cows can legally build. Because every bale is one unit tall, the height of a tower equals the number of bales it contains.

Input

Line 1: A single integer $N$ .
Lines 2 to $N+1$ : Each line contains two space-separated integers, the width and the breadth of one bale.

Output

Line 1: The height of the tallest tower that can legally be built from the bales.

Hint

In the example, five of the six bales can be stacked into a tower of height $5$ , and another valid stacking of the same height also exists.

Examples1

Example 1
Input
```
6
6 9
10 12
9 11
8 10
7 8
5 3
```
Expected output
```
5
```