Себек мстить сусідам

Ох і навитворяли ті сусіди. Так сильно ненавиділи Себека, робили йому різні пастки і неприємності. І ось, нарешті, Себеку наснився сон. Не простий, а той, в якому він може вигнати всіх сусідів з дому.

Дім Себека має форму кола, поділеного на квартири. Всього в будинку $n$ квартир, пронумерованих від $1$ до $n$ за годинниковою стрілкою. Наступною після квартири з номером $1\le i\le n-1$ знаходиться квартира з номером $i+1$, а після квартири $n$ знаходиться квартира $1$. У квартирі з номером $i$ живе $a_i$ сусідів.

Щоб виганяти мешканців з дому Себек може $k$ разів запустити жабу в якусь з квартир. Потужність всіх жаб — ціле число від $0$ до $4$ і дорівнює $m$ для всіх жаб. Себек не обов'язково кожен раз запускає жаб в одну й ту ж саму квартиру. Коли Себек запускає жабу в квартиру з номером $i$, то ті сусіди, що в цей момент часу знаходяться у квартирі $i$ тікають з дому назавжди. Також сусіди з $m$ наступних квартир за годинниковою стрілкою лякаються і переселяються у $m+1$-шу наступну квартиру за годинниковою стрілкою. Так само і проти годинникової стрілки. Сусіди з $m$ попередніх квартир проти годинникової стрілки лякаються і переселяються у $m+1$-шу попередню квартиру проти годинникової стрілки.

Тобто, якщо в будинку $7$ квартир і жаба полетіла у квартиру з номером $6$, а $m=1$, то з шостої квартирі всі зникнуть назавжди, з сьомої квартири мешканці переселяться в першу, а з п'ятої квартири переселяться в четверту. Якщо $m=0$, то ніхто нікуди не переселяється, просто сусіди з квартири $i$ тікають.

Внизу зображено три рисунки для $n=8$ і $m=2$. На першому зображено початкову кількість сусідів в кожній квартирі. На другому — кількість сусідів після того, як жаба полетіла в квартиру $5$. На третьому зображено розселення після того, як ще одна жаба полетіла в квартиру $2$. Навколо будинку написані номери квартир. Жовтим кольором виділено квартиру в яку летить жаба.

Звичайно, Себек хоче вигнати з дому якнайбільше сусідів. Але він ще недостатньо розумний, тому просить вас допомогти йому і сказати максимальну кількість сусідів, яку можна вигнати з дому за $k$ запусків жаб.

Input

Перший рядок містить три цілі числа $n$, $k$ та $m$ ($0\le m\le 4,2\cdot m+3\le n\le 2000,1\le k\le n$) — кількість квартир у будинку, кількість запусків жаб та потужність жаб відповідно.

Другий рядок містить $n$ цілих чисел $a_i$ ($0\le a_i\le 1000000$) — кількість мешканців у квартирах.

Третій рядок містить одне ціле число $g$ ($0\le g\le 10$) — номер блоку, до якого належить тест.

Output

В єдиному рядку виведіть одне ціле число — максимальну кількість сусідів, яку може вигнати Себек.

Examples

Scoring

1. ($10$ балів) $m=0$.

2. ($10$ балів) $n\le 11$.

3. ($10$ балів) $m\le 1$, при цьому в перших $m$ квартирах і в останніх $m$ квартирах ніхто не живе.

4. ($10$ балів) $m\le 2$, при цьому в перших $m$ квартирах і в останніх $m$ квартирах ніхто не живе.

5. ($10$ балів) $m\le 1$, при цьому усі квартири пусті або існують такі $m+1\le l\le r\le n-m$, що на відрізку квартир від $l$ до $r$ живуть по одному сусіду, а у всіх інших квартирах ніхто не живе.

6. ($10$ балів) $m\le 1$, при цьому або виконуються умови блоку $5$, або існують такі $m+1\le l_1\le r_1<$ $<l_2\le r_2\le n-m$, що на відрізках квартир від $l_1$ до $r_1$ та від $l_2$ до $r_2$ живуть по одному сусіду, у всіх інших квартирах ніхто не живе, і $m+1\le l_2-r_1$.

7. ($10$ балів) $m\le 1$.

8. ($10$ балів) $m\le 2$.

9. ($10$ балів) $m\le 3$.

10. ($10$ балів) Без додаткових обмежень.