POSTERIN - Postering

All the buildings in the east district of Byteburg were built in accordance with the old architecture: they stand next to each other with no spacing in between. Together they form a very long chain of buildings of diverse height, extending from east to west.

The mayor of Byteburg, Byteasar, has decided to have the north face of the chain covered with posters. Byteasar ponders over the minimum number of posters sufficient to cover the whole north face. The posters have rectangular shape with vertical and horizontal sides. They cannot overlap, but may touch each other, i.e. have common points on the sides. Every poster has to entirely adjoin the walls of certain buildings and the whole surface of the north face has to be covered.

Task

Write a programme that:

  • reads the description of buildings from the standard input,
  • determines the minimum number of posters needed to entirely cover their north faces,
  • writes out the outcome to the standard output.

Input

The first line of the standard input contains one integer N (1 <= N <= 250000), denoting the number of buildings the chain comprises of. Each of the following N lines contains two integers Di and Wi (1 <= Di, Wi <=109), separated by a single space, denoting respectively the length and height of the i-th building in the row.

Output

The first and only line of the standard output should contain one integer, the minimum number of rectangular posters that suffice to cover the north faces of the buildings.

Example

Input
5
1 2
1 3
2 2
2 5
1 4

Output
4

Added by:Sergey Kulik
Date:2013-08-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:POI XV

hide comments
2024-03-07 06:09:11
length is not important
2022-02-20 07:28:10
Very bad problem :(((

Last edit: 2022-02-20 07:28:20
2021-10-12 11:25:48
Use Stack ;)

Last edit: 2021-10-12 11:26:50
2020-11-29 19:22:13
A square is also a rectangle.
2020-06-06 10:31:04
Hint:
Maintain a stack of currently running strips of posters and push and pop strips according to the size of the buildings as you iterate over them from left to right.
And also increase a count variable which would end up as your final answer.
2017-10-17 13:06:58 Sergej
Please check your test data or problem description (condition)

Last edit: 2017-12-16 13:20:04
2013-08-24 19:07:49 Simes
These are the shapes of the five buildings (underscore used to retain spacing!)
____44
____445
_2__445
1233445
1233445

Which can be covered with four posters like this:
____AA
____BBB
_D__BBB
CCCCCCC
CCCCCCC

or
____AA
____AAB
_D__AAB
CCCCAAB
CCCCAAB

or
____AA
____AAB
_D__AAB
CCCCCCC
CCCCCCC

(Sorry for the messy diagrams, can't get fixed width font or code tag to display.)

Last edit: 2013-08-24 19:20:13
2013-08-19 15:42:47 Arpit Rathi
can anyone tell hw the output is coming
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.