Sadzenie bulw
Limit pamięci: 32 MB
Farmer Bulwęsadź musi obsadzić swoje pola bulwami.
Każde pole ma określoną bulwonasyconość wyrażającą się liczbą całkowitą .
Jeżeli zasadzi się na tym polu bulw, gdzie , to plon
wyniesie . Jeżeli zasadzi się na tym polu więcej niż bulw, to plonu nie będzie
ze względu na wzajemne zagłuszanie.
Farmer nie za dobrze radzi sobie z matematyką, a ma ograniczony zasób bulw.
Powiedz mu, jak ma zasadzić swoje bulwy, żeby osiągnąć maksymalny plon.
Zakładamy, że farmer nie musi zasadzać wszystkich bulw.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (),
oznaczającą liczbę pól Bulwęsadzia.
Następny wiersz zawiera liczb całkowitych
(), gdzie oznacza
bulwonasyconość -tego pola.
Ostatni wiersz zawiera jedną liczbę całkowitą (),
oznaczającą liczbę bulw, które posiada Bulwęsadź.
Wyjście
W jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita,
oznaczająca maksymalny łączny plon Bulwysadzia.
Przykład
Dla danych wejściowych:
1
9
3
poprawną odpowiedzią jest:
9
Autor zadania: Joachim Jelisiejew.