Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

OI15_PLA - Plakatowanie

Wszystkie budynki we wschodniej części Bajtogrodu zostały zbudowane zgodnie z zasadami starego bajtobudownictwa: stoją one jeden przy drugim (nie ma między nimi przerw). Razem tworzą bardzo długą ścianę budynków o zróżnicowanej wysokości, ciągnącą się ze wschodu na zachód.

Burmistrz Bajtogrodu, Bajtazar, postanowił że ścianę budynków należy od północnej strony pokryć plakatami. Bajtazar zastanawia się, jaką minimalną liczbą plakatów można pokryć całą północną ścianę budynków. Plakaty mogą mieć kształt prostokątów o bokach pionowych i poziomych. Plakaty nie mogą zachodzić na siebie, natomiast mogą stykać się brzegami. Każdy plakat musi w całości przylegać do ścian pewnych budynków i cała powierzchnia północnych ścian budynków musi być pokryta plakatami.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opisy budynków,
  • wyznaczy minimalną liczbę plakatów, potrzebnych do całkowitego pokrycia ich północnych ścian,
  • wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę budynków stojących w rzędzie. Kolejne wierszy zawiera po dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające długość i wysokość -tego budynku w rzędzie.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, minimalną liczbę prostokątnych plakatów, którymi można całkowicie pokryć północne ściany budynków.

Przykład

Dla danych wejściowych:

5
1 2
1 3
2 2
2 5
1 4

poprawną odpowiedzią jest:

4

Na rysunkach została przedstawiona sama północna ściana rzędu budynków. Drugi z rysunków przedstawia przykładowe pokrycie ściany czterema plakatami.

Autor zadania: Jakub Radoszewski.


Dodane przez:Romualda Laskowska
Data dodania:2010-10-27
Limit czasu wykonania programu:0.100s-0.300s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU NODEJS OBJC VB.NET
Pochodzenie:Olimpiada Informatyczna
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.