409467: GYM103567 F Метро

F. Метроограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Паровозик Томас устроился поездом в московское метро. Он будет работать на кольцевой линии. За свою рабочую смену он должен проехать свой маршрут ровно $$$k$$$ раз подряд.

Маршрут начинается и заканчивается на станции Октябрьская. Весь маршрут поезд проезжает за $$$d$$$ минут. Как только поезд заканчивает маршрут, он тут же отправляется на новый. Соответственно, если поезд начал маршрут во время $$$t$$$, то на следующий маршрут он отправится ровно во время $$$t + d$$$, не раньше и не позже.

Томас нашел статистику загруженности поездов: если поезд начал маршрут в момент времени $$$i$$$, то в поезд зайдет $$$a_i$$$ пассажиров на всем маршруте. Всего за день будет выполнено $$$n$$$ маршрутов - в $$$1$$$-ю, $$$2$$$-ю, $$$\dots$$$, $$$n$$$-ю минуты.

Томасу стало интересно, в какой момент времени начинается самая загруженная смена. Загруженность смены равна суммарному количеству зашедших в поезд пассажиров по всем $$$k$$$ маршрутам, которые Томас проедет.

Гарантируется, что всегда существует хотя бы одна смена, за которую можно проехать маршрут $$$k$$$ раз подряд.

Входные данные

В первой строке записано одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$  — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Каждый из наборов входных данных задаётся следующим образом.

В первой строке следуют три целых числа $$$n, k, d$$$ $$$(1 \le n, k, d \le 2 \cdot 10^5)$$$  — общее количество отправляющихся на маршрут поездов за день, количество маршрутов в трудовых обязанностях Томаса и продолжительность одного маршрута.

Во второй строке следует $$$n$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$  — количество пассажиров, зашедших в поезд на маршруте, начавшемся в момент времени $$$i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Гарантируется, что всегда существует хотя бы одна смена, за которую можно проехать маршрут $$$k$$$ раз.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество пассажиров, которых можно перевести за одну смену.

ПримерВходные данные

2
10 3 2
2 3 4 9 8 7 6 1 5 10
10 3 3
1 1 1000000000 1 1 1000000000 1 1 1000000000 1

Выходные данные

19
3000000000

Примечание

В первом наборе входных данных существуют следующие возможные смены из $$$k = 3$$$ маршрутов с продолжительностью $$$d = 2$$$:

1. ($$$2$$$, $$$4$$$, $$$8$$$)  — сумма $$$14$$$;
2. ($$$3$$$, $$$9$$$, $$$7$$$)  — сумма $$$19$$$;
3. ($$$4$$$, $$$8$$$, $$$6$$$)  — сумма $$$18$$$;
4. ($$$9$$$, $$$7$$$, $$$1$$$)  — сумма $$$17$$$;
5. ($$$8$$$, $$$6$$$, $$$5$$$)  — сумма $$$19$$$;
6. ($$$7$$$, $$$1$$$, $$$10$$$)  — сумма $$$18$$$.

Максимальное количество перевезенных пассажиров достигается на сменах, начатых во $$$2$$$-й и $$$5$$$-й моменты времени.

Во втором наборе входных данных существуют только $$$4$$$ возможные смены из $$$k = 3$$$ маршрутов с продолжительностью $$$d = 3$$$:

1. ($$$1$$$, $$$1$$$, $$$1$$$)  — сумма $$$3$$$;
2. ($$$1$$$, $$$1$$$, $$$1$$$)  — сумма $$$3$$$;
3. ($$$1000000000$$$, $$$1000000000$$$, $$$1000000000$$$)  — сумма $$$3000000000$$$;
4. ($$$1$$$, $$$1$$$, $$$1$$$)  — сумма $$$3$$$.

Максимальное количество людей будет перевезено за смену $$$3$$$ и только за неё.