Is Bigger Smarter?

Time limit1sMemory limit128 MB

Summary
Given pairs of weight and IQ for up to 1000 elephants, find the largest subset whose weights strictly increase while IQs strictly decrease.
Level

Medium4 of 10

Topics
Dynamic programming, Sorting
Solved
No attempts yet

Problem

Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to take the data on a collection of elephants and select as large a subset as possible that can be arranged in a sequence so that the weights are strictly increasing while the IQs are strictly decreasing.

Input

The input consists of data for several elephants, one elephant per line, terminated by the end-of-file. The data for a particular elephant is a pair of integers: the first is its weight in kilograms and the second is its IQ in hundredths of an IQ point. Both integers are between 1 and 10000. The data contains information for at most 1000 elephants. Two elephants may have the same weight, the same IQ, or even the same weight and IQ.

Output

Let the weight and IQ of the ii-th elephant be W[i]W[i] and S[i]S[i]. Consider choosing a subset of elephants that can be ordered as a[1],a[2],…,a[n]a[1], a[2], \ldots, a[n] so that

W[a[1]]<W[a[2]]<⋯<W[a[n]]W[a[1]] < W[a[2]] < \cdots < W[a[n]]

and

S[a[1]]>S[a[2]]>⋯>S[a[n]]S[a[1]] > S[a[2]] > \cdots > S[a[n]]

All inequalities are strict: the weights must be strictly increasing and the IQs must be strictly decreasing. Output a single line containing the maximum possible number of elephants nn in such a subset.

Examples2

  1. Example 1

    Input
    6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
    Expected output
    4

  2. Example 2

    Input
    1 5
2 4
3 3
4 2
5 1
    Expected output
    5