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:

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.

#8335 upload 351 done 119 how_to_reg 95 call_split Subtarea

포스터 붙이기 timer 1s memory 1024MB

#8335
Subtarea

포스터 붙이기 1s 1024MB