In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
Write a programme that:
The first line of the standard input contains one integer (), denoting the number of buildings the chain comprises of. Each of the following lines contains two integers and (), separated by a single space, denoting respectively the length and height of the building in the row.
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.
For the input data:
5 1 2 1 3 2 2 2 5 1 4
the correct result is:
The figures show the north face of the buildings chain. The second figure shows an exemplary covering of the face with four posters.
Task author: Jakub Radoszewski.