Ох і навитворяли ті сусіди. Так сильно ненавиділи Себека, робили йому різні пастки і неприємності. І ось, нарешті, Себеку наснився сон. Не простий, а той, в якому він може вигнати всіх сусідів з дому.
Дім Себека має форму кола, поділеного на квартири. Всього в будинку квартир, пронумерованих від до за годинниковою стрілкою. Наступною після квартири з номером 1\leq i \leq n-1 знаходиться квартира з номером i+1, а після квартири знаходиться квартира . У квартирі з номером живе a_i сусідів.
Щоб виганяти мешканців з дому Себек може разів запустити жабу в якусь з квартир. Потужність всіх жаб — ціле число від до і дорівнює для всіх жаб. Себек не обов'язково кожен раз запускає жаб в одну й ту ж саму квартиру. Коли Себек запускає жабу в квартиру з номером , то ті сусіди, що в цей момент часу знаходяться у квартирі тікають з дому назавжди. Також сусіди з наступних квартир за годинниковою стрілкою лякаються і переселяються у m+1-шу наступну квартиру за годинниковою стрілкою. Так само і проти годинникової стрілки. Сусіди з попередніх квартир проти годинникової стрілки лякаються і переселяються у m+1-шу попередню квартиру проти годинникової стрілки.
Тобто, якщо в будинку квартир і жаба полетіла у квартиру з номером , а m=1, то з шостої квартирі всі зникнуть назавжди, з сьомої квартири мешканці переселяться в першу, а з п'ятої квартири переселяться в четверту. Якщо m=0, то ніхто нікуди не переселяється, просто сусіди з квартири тікають.
Внизу зображено три рисунки для n=8 і m=2. На першому зображено початкову кількість сусідів в кожній квартирі. На другому — кількість сусідів після того, як жаба полетіла в квартиру . На третьому зображено розселення після того, як ще одна жаба полетіла в квартиру . Навколо будинку написані номери квартир. Жовтим кольором виділено квартиру в яку летить жаба.

Звичайно, Себек хоче вигнати з дому якнайбільше сусідів. Але він ще недостатньо розумний, тому просить вас допомогти йому і сказати максимальну кількість сусідів, яку можна вигнати з дому за запусків жаб.
Перший рядок містить три цілі числа , та (0 \leq m \leq 4,\, 2 \cdot m+3 \leq n \leq 2\,000,\, 1 \leq k \leq n) — кількість квартир у будинку, кількість запусків жаб та потужність жаб відповідно.
Другий рядок містить цілих чисел a_i (0 \leq a_i \leq 1\,000\,000) — кількість мешканців у квартирах.
Третій рядок містить одне ціле число (0 \leq g \leq 10) — номер блоку, до якого належить тест.
В єдиному рядку виведіть одне ціле число — максимальну кількість сусідів, яку може вигнати Себек.
Example 1
Example 2
( балів) m = 0.
( балів) n \leq 11.
( балів) m \leq 1, при цьому в перших квартирах і в останніх квартирах ніхто не живе.
( балів) m \leq 2, при цьому в перших квартирах і в останніх квартирах ніхто не живе.
( балів) m \leq 1, при цьому усі квартири пусті або існують такі m + 1 \leq l \leq r \leq n - m, що на відрізку квартир від до живуть по одному сусіду, а у всіх інших квартирах ніхто не живе.
( балів) m \leq 1, при цьому або виконуються умови блоку , або існують такі 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.
( балів) m \leq 1.
( балів) m \leq 2.
( балів) m \leq 3.
( балів) Без додаткових обмежень.