Доставка reshite

C. Доставка Ограничение времени 1 секунда Ограничение памяти 256Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Евгений — логист, и у него есть n товаров. За продажу i -го товара компания получит a i монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики. Формат ввода Первая строка содержит три целых числа n , k и s ( 1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ 1 0 , 1 ≤ s ≤ 1 0 9 ) — количество товаров, а также числа k и s . Вторая строка содержит n целых чисел a 1 , a 2 , … , a n ( − 1 0 9 ≤ a i ≤ 1 0 9 ) — стоимости товаров.

Формат вывода Выведите одно число — максимальное количество монет, которое может получить Евгений Пример 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 монет на один грузовик. Во втором примере оптимально выбрать любой отрезок из двух товаров. В третьем примере не получится доставить ни одного товара так, чтобы получить прибыль. В четвертом примере оптимально будет выбрать отрезок от второго товара до восьмого.