Grzyby po deszczu [B]

Limit pamięci: 32 MB

Nad Bajtowym Lasem spadł rzęsisty deszcz. Bajtazar, zapalony grzybiarz, skorzystał z okazji i wybrał się na grzyby.

Bajtazar zna ścieżkę prowadzącą przez las, która przechodzi przez szereg polan wyjątkowo obfitujących w grzyby. Każde dwie kolejne polany na ścieżce są w tej samej odległości od siebie - Bajtazar potrzebuje piętnastu minut, by przejść pomiędzy parą sąsiednich polan na ścieżce. Po dojściu do polany Bajtazar, jak każdy szanujący się grzybiarz, zbiera rosnące tam grzyby w pomijalnie małym czasie. Jak powszechnie wiadomo, grzyby po deszczu rosną szybko i już po pół godziny od ich zebrania odrastają.

Znając liczby grzybów na poszczególnych polanach, czas trwania spaceru Bajtazara oraz wiedząc, że idzie on trasą zapewniającą mu największe możliwe zbiory, oblicz, ile grzybów trafi do jego koszyka. Bajtazar może zakończyć spacer w dowolnym miejscu ścieżki.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (), oznaczające liczbę polan na ścieżce oraz czas trwania spaceru Bajtazara w kwadransach. Drugi wiersz zawiera ciąg liczb całkowitych (), określających liczby grzybów na kolejnych polanach, przez które przechodzi ścieżka. Bajtazar rozpoczyna spacer przy pierwszej spośród opisanych polan. Zakładamy, że może zbierać grzyby zarówno tuż przed pierwszym, jak i tuż po -tym kwadransie grzybobrania.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą - maksymalną liczbę grzybów, jakie Bajtazar może zebrać w trakcie spaceru.

Przykład

Dla danych wejściowych:

5 4
3 4 3 5 1

poprawną odpowiedzią jest:

18

Wyjaśnienie do przykładu: Optymalna trasa grzybobrania Bajtazara, która zajmuje 60 minut, pozwala zebrać łącznie 18 grzybów: 3 w chwili 0, 4 po 15 minutach, 3 po 30 minutach, 5 po 45 minutach, wreszcie 3 po 60 minutach.

Autor zadania: Jakub Łącki.