UVa 10131

Summary

A standard Dynamic Programming (Longest Increasing Subsequence) problem.

Explanation

This can also be viewed as a Graph Theory problem, as the Longest Increasing Subsequence problem reduces to finding the longest path in a Directed Acyclic Graph. Therefore, this problem can be solved in ${\displaystyle O(nlogn)}$. Using each elephant as a vertex, an edge can be drawn from a bigger, smarter (strictly) elephant to one that is less so.

Input

```6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
```

```4
4
5
9
7
```