Króliki
Limit pamięci: 256 MB
Bajtazar postanowił zacząć żyć ekologicznie, i został hodowcą sałaty.
Jak wiadomo, bajtockie króliki uwielbiają sałatę, nic więc
dziwnego, że wkrótce zawitały one do ogródka Bajtazara.
Wokół domu Bajtazara rozmieszczone jest
grządek sałaty, które będziemy
numerować od
do
.
Każde dwie kolejne grządki sąsiadują ze sobą, tzn. dla każdego
grządki o numerach
oraz
sąsiadują ze sobą.
Dodatkowo, grządka o numerze
sąsiaduje z grządką o numerze
.
Na grządce o numerze
siedzi
królików i pałaszuje sałatę Bajtazara.
Bajtazar chciałby przegonić z ogródka jak najwięcej królików.
Ma do dyspozycji swoją starą, wierną strzelbę, w której jest
nabojów.
Króliki są bardzo płochliwe, więc gdy tylko Bajtazar wystrzeli
w kierunku grządki o numerze
, to wszystkie króliki z tej grządki
uciekają w siną dal.
Co więcej, przestraszone króliki z obu sąsiednich grządek
przeskakują na dalsze grządki, tzn. kicają na grządkę sąsiadującą
z tą, na której stoją - oczywiście nie tą, w kierunku której strzelał Bajtazar.
Pomóż Bajtazarowi i wyznacz maksymalną liczbę królików, które może on
wygonić z ogródka za pomocą co najwyżej
strzałów.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
i
(
,
),
oznaczające liczbę grządek w ogródku i liczbę nabojów w strzelbie Bajtazara.
W drugim wierszu znajduje się ciąg liczb całkowitych
(
), które oznaczają liczby królików
na kolejnych grządkach.
Wyjście
Na wyjście należy wypisać jedną liczbę całkowitą -
maksymalną liczbę królików, które Bajtazar jest w stanie przegonić z ogródka.
Przykład
Dla danych wejściowych:
5 2
6 1 5 3 4
poprawną odpowiedzią jest:
13
Wyjaśnienie do przykładu:
Bajtazar przegania 6 królików z grządki numer 1
(wskutek czego króliki z grządki numer 5 przeskakują na grządkę numer 4,
zaś króliki z grządki numer 2 przeskakują na grządkę numer 3),
a następnie przegania 7 królików z grządki numer 4.
Autor zadania: Tomasz Idziaszek.