Plakatowanie
Limit pamięci: 32 MB
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.