Превышение лимит времени. Как сделать скорость по меньше?

Я написал правильно код
примеры правильно выводит:

import math

n, k, s = map(int, input().split())
a = list(map(int, input().split()))
max_coins = 0
for i in range(n):
for j in range(i + 1, n + 1):
coins = sum(a[i:j]) - math.ceil(len(a[i:j]) / k) * s
if coins > max_coins:
max_coins = coins

print(max_coins)

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

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

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

Можете подсказать, как уменьшить скорость для времени, чтобы не так быстро выводил?

 p, k, s = (int(t) for t in input().split())

a = list(int(t) for t in input().split())



max_profit = 0

maxp = [0] * k

for i in range(k - 1):

    m = min(k, i + 1)

    maxp = [max(maxp[-1] + a[i], 0) - s] + [max(maxp[i - 1] + a[i], -s) for j in range(1, m)] + [0] * (k - m)

for i in range(k - 1, p):

    maxp = [max(maxp[-1] + a[i], 0) - s] + [max(maxp[j - 1] + a[i], -s) for j in range(1, k)]

    max_profit = max(*maxp, max_profit)



print(max_profit) 

 p, k, s = (int(t) for t in input().split())

a = (int(t) for t in input().split())



max_profit = 0

maxp = [0] * k

for i in range(k - 1):

    m = min(k, i + 1)

    e = next(a)

    maxp = [max(maxp[-1] + e, 0) - s] + [max(maxp[i - 1] + e, -s) for j in range(1, m)] + [0] * (k - m)

for i in range(k - 1, p):

    e = next(a)

    maxp = [max(maxp[-1] + e, 0) - s] + [max(maxp[j - 1] + e, -s) for j in range(1, k)]

    max_profit = max(*maxp, max_profit)



print(max_profit)