Составить программу на Python

Доставка

Евгений — логист, и у него есть n товаров. За продажу i-го товара компания получит ai монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики.

Первая строка содержит три целых числа n, k и s (1≤n≤105,1≤k≤10,1≤s≤109) — количество товаров, а также числа k и s.

Вторая строка содержит n целых чисел a1,a2,…,an (−109≤ai≤109) — стоимости товаров.

Выведите одно число — максимальное количество монет, которое может получить Евгений

Пример 1

6 3 10

0 -4 16 -7 3 8

6

Пример 2

3 2 10

9 9 9

8

Пример 3

5 3 15

3 2 4 5 1

0

Пример 4

10 3 5

-3 9 7 15 -10 9 7 6 -1 0

28

Примечания

В первом примере оптимально будет выбрать только товар со стоимостью 16 и потратить 10 монет на один грузовик.

Во втором примере оптимально выбрать любой отрезок из двух товаров.

В третьем примере не получится доставить ни одного товара так, чтобы получить прибыль.

В четвертом примере оптимально будет выбрать отрезок от второго товара до восьмого.