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.