Information

Deadline No deadline
Submission limit No limitation

Sign in

Contest 1 2019 - B


Money != Happnyess

A lot of people believe that money equates to happiness so that the more money you have the happier you are.

You do not believe that this is the case and to prove your point to interviewed $n$ people by asking them how much money they make each month and to evaluate how happy they feel. Now you want to find the largest subset of interviewed people such that if you list them sorted by monthly income, these incomes are in strictly increasing order and their happiness levels are sorted in strictly decreasing order.

Example

The table on the left shows the first sample input. The largest subset with of people with the above conditions has 4 elements. One possible solution is the take people at indexes 4, 5, 9, 8. When we list those people in incresing order of income, the incomes are strictly increasing and their happiness strictly decreasing as shown on the table on the right.

contest1-2019-B/table.png

Input

The first line contains a single integer \(n\) giving the number of people you interviewed.

The follow \(n\) lines each with two integers \(m\) and \(h\) giving the income and happiness of the \(n\) persons.

Constraints

  • \(1 \leq n \leq 1000\)
  • \(1 \leq m, h \leq 10000\)

Output

A single line with the size of the largest subset of people such that when sorted by income, their incomes form a strictly increasing sequence and their happiness levels form a strictly decreasing sequence.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Max file size: 1.0 MiB
Allowed extensions: .java, .cpp, .py