22841_HungryCows

he cows are lined up at their feed trough, which has individualized feeding buckets numbered sequentially from 1 through N (1 ≤ N ≤ 2000). Each night a lucky cow gets to eat from a number of buckets according to Farmer John's rules.

Farmer John posts a list of no more than B bucket-sequences (a bucket sequence is a pair of integers (a pair like start-end where 1 ≤ start ≤ end ≤ N and the sequence includes buckets start through end, e.g., 1-3, 7-8, 3-4). FJ's rules allow the cow to choose as many of the intervals as she wishes, as long as no bucket is mentioned more than once in the total set of chosen intervals.

Of course, cows are like anyone else and want as much feed as they can get. Given a set of bucket-sequences, help the lucky cow find the best sequence which yields the greatest amount of feed.

In the example above, bucket-sequences 1-3 and 3-4 overlap; the wise cow chooses the set of {1-3, 7-8} for a lavish dinner of five buckets.

* Line 1: One integer B (1 ≤ B ≤ 1000)

* Lines 2..B+1: Each line contains a two integer bucket sequence with the smaller bucket number first

A single line with a single integer that is the greatest number of feed buckets the lucky cow can eat.

3
1 3
7 8
3 4

5