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

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

Формат ввода

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

Вторая строка содержит n целых чисел a_1, a_2, …, a_n (−10^9 ≤ a_i ≤ 10^9) — стоимости товаров.

Формат вывода

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

тесты

10 3 5

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

правильный ответ - 28 (нужно выбрать отрезок [2; 8], сумма на нем 43 и заплатить за грузовики (3 грузовика нужно, чтобы увести 7 элементов), то есть 15 => 43 -15 = 28)

6 3 10

0 -4 16 -7 3 8

правильный ответ - 6 (выбрать отрезок [3; 3], сумма на нем 16 и заплатить за один грузовик 10 => 16 - 10 = 6)

3 2 10

9 9 9

правильный ответ - 8 (выбрать отрезок [1; 2] или [2; 3], сумма на них 18 и заплатить за один грузовик 10 => 18 - 10 = 8)