Олимпиадный тренинг

Задача 27071. PYRAMID


Задача

Темы:
To build a two-dimensional pyramid, rectangular blocks are used, each of which is characterized by a width and height. You can put one block on top of another only if the width of the top block is strictly less than the width of the bottom one. The bottommost block in the pyramid can be any width block.

Given a set of blocks, it is required to determine the maximum height pyramid that can be built from them.

Input data format
The first line of the input contains the number N – the number of blocks ( 1 <= N <= 100000 ). The next N lines contain pairs of integers wi and hi ( 1<= wi , hi <= 109), space-separated – block width and height, respectively.

Output data format
Integer – the maximum height of the pyramid.

Enter Output
3
3 1
2 2
3 3
5

Note.
In the above example, the pyramid will consist of two blocks: the bottom block will be number 3, and the top one will be – block number 2. Block number 1 cannot be used to build a pyramid, because. its width is the same as the width of the bottom block.