Евгений — логист, и у него есть n товаров. За продажу i-го товара компания получит ai монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики.
Формат ввода
Первая строка содержит три целых числа n, k и s (1≤n≤10^5,1≤k≤10,1≤s≤10^9) — количество товаров, а также числа k и s.
Вторая строка содержит n целых чисел a1,a2,…,an (−10^9≤ai≤10^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 монет на один грузовик.
Во втором примере оптимально выбрать любой отрезок из двух товаров.
В третьем примере не получится доставить ни одного товара так, чтобы получить прибыль.
В четвертом примере оптимально будет выбрать отрезок от второго товара до восьмого.