Wieża
Limit pamięci: 64 MB
Bajtazar od dziecka marzył o sięgnięciu chmur. Teraz jego marzenie może się
wreszcie spełnić.
Aby osiągnąć swój cel, Bajtazar kupił pustaków
ponumerowanych liczbami od do . Pustaki mają taką samą wysokość,
lecz mogą różnić się szerokościami.
Planuje zbudować z nich wielopoziomową wieżę w taki sposób, aby na każdy poziom
składało się kilka pustaków, a sumaryczna szerokość każdego poziomu była nie większa
niż sumaryczna szerokość poziomu znajdującego się bezpośrednio pod nim (o ile taki
istnieje). Bajtazar jest także głęboko przekonany, że wieża zawali się, jeśli pewien pustak
znajdzie się na wyższym poziomie niż pustak o większym numerze.
Kawalerka Bajtazara jest za mała do przechowywania pustaków, więc do zbudowania
wieży musi on użyć wszystkich pustaków będących w jego posiadaniu.
Przed zabraniem się do pracy, Bajtzar poprosił Cię o obliczenie, jaka jest największa
możliwa wysokość wieży, którą jest w stanie zbudować, zachowując wymienione warunki.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita
() oznaczająca liczbę kupionych przez Bajtazara pustaków.
W drugim wierszu wejścia znajduje się liczb całkowitych ();
liczba oznacza szerokość pustaka o numerze .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba
całkowita równa maksymalnej wysokości wieży, jaką może zbudować Bajtazar.
Przykład
Dla danych wejściowych:
3
1 2 3
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: Na najniższym poziomie wieży Bajtazar może
ułożyć pustaki o numerach i , natomiast na drugim poziomie - pustak o numerze .
Autor zadania: Brian Dean (zapożyczenie z USACO: Adam Karczmarz).