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

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 256 мегабайтів

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

Дім Себека має форму кола, поділеного на квартири. Всього в будинку $n$ квартир, пронумерованих від $1$ до $n$ за годинниковою стрілкою. Наступною після квартири з номером $1 \leq i \leq 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$ запусків жаб.

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Оцінювання

( $10$ балів) $m = 0$ .
( $10$ балів) $n \leq 11$ .
( $10$ балів) $m \leq 1$ , при цьому в перших $m$ квартирах і в останніх $m$ квартирах ніхто не живе.
( $10$ балів) $m \leq 2$ , при цьому в перших $m$ квартирах і в останніх $m$ квартирах ніхто не живе.
( $10$ балів) $m \leq 1$ , при цьому усі квартири пусті або існують такі $m + 1 \leq l \leq r \leq n - m$ , що на відрізку квартир від $l$ до $r$ живуть по одному сусіду, а у всіх інших квартирах ніхто не живе.
( $10$ балів) $m \leq 1$ , при цьому або виконуються умови блоку $5$ , або існують такі $m + 1 \leq l_{1} \leq r_{1} <$ $< l_{2} \leq r_{2} \leq n - m$ , що на відрізках квартир від $l_{1}$ до $r_{1}$ та від $l_{2}$ до $r_{2}$ живуть по одному сусіду, у всіх інших квартирах ніхто не живе, і $m + 1 \leq l_{2} - r_{1}$ .
( $10$ балів) $m \leq 1$ .
( $10$ балів) $m \leq 2$ .
( $10$ балів) $m \leq 3$ .
( $10$ балів) Без додаткових обмежень.