#A188. [POI2008]PLA-Postering


No testdata at current.


All the buildings in the east district of Byteburg were built in accordance with the old arbitecture:

they stand next to each other with no spacing inbetween.

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.



The first line of the standard input contains one integer nn (1n250 0001\le n\le 250\ 000), denoting the number of buildings the chain comprises of.

Each of the following nn lines contains two integers did_i and wiw_i (1di,wi1 000 000 0001\le d_i,w_i\le 1\ 000\ 000\ 000), separated by a single space, denoting respectively the length and height of the ithi^{th} building in the row.

第一行为一个整数n(1≤n≤250000),表示有n个建筑,接下来n行中,第i行表示第i个建筑物的宽di与高wi(1≤di,wi≤1 000 000 000),中间由一个空格隔开


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.


1 2
1 3
2 2
2 5
1 4


题目简述:N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.