A sample task used in our recruitment process

Posters

Memory limit: 32 MB

All the buildings in the eastern part of Byteville have been constructed according to the rules and principles of the old byteconstruction: they stand next to each other (no gaps in between). They form a very long wall of buildings having diverse heights, extending from the east to the west.

The Mayor of Byteville, Bytehazar, decided that the north-facing wall of the buildings should be covered with posters. Bytehazar wonders what is the minimum number of posters to cover the entire northern wall of the buildings. Posters can have the shape of rectangles with vertical and horizontal sides. Posters may not overlap but they can contact along their edges. The whole of each poster shall touch the walls of some buildings and the entire surface of northern walls
of building shall be covered with posters.

Task

Write a program which  will:

  • load building descriptions from a standard input,
  • determine the minimum number of posters required to cover fully the northern walls,
  • provide the result to a standard output.

Input

The first input line contains one integer number n (1 < n < 250 000), representing the number of buildings standing in a row. The following n lines contain two integer numbers ^ each (1 < d^u^ < 1000 000 000), separated with a single space and representing the length and height of i-th building in the row.

Output

The single output line should contain a single integer, minimum number of rectangular posters
to cover fully the northern walls of the buildings.

Example

For input data:

The right answer is:

The drawings show solely the northern wall of the building row. The second drawing shows an example of four posters covering the wall.