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 D_{i} and W_{i} (1 <= D_{i}, W_{i }<=10^{9}), separated by a single space, denoting respectively the length and height of the ith 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
hide comments
omar_hafez:
20220220 07:28:10
Very bad problem :((( Last edit: 20220220 07:28:20 

nikman_hunter9:
20211012 11:25:48
Use Stack ;) Last edit: 20211012 11:26:50 

karan_221:
20201129 19:22:13
A square is also a rectangle. 

jenishmonpara:
20200606 10:31:04
Hint:


Sergej:
20171017 13:06:58
Please check your test data or problem description (condition) Last edit: 20171216 13:20:04 

Simes:
20130824 19:07:49
These are the shapes of the five buildings (underscore used to retain spacing!)


Arpit Rathi:
20130819 15:42:47
can anyone tell hw the output is coming

Added by:  Tooru Ichii 
Date:  20130811 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  POI XV 