409467: GYM103567 F Метро
Description
Паровозик Томас устроился поездом в московское метро. Он будет работать на кольцевой линии. За свою рабочую смену он должен проехать свой маршрут ровно $$$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$$$:
- ($$$2$$$, $$$4$$$, $$$8$$$) — сумма $$$14$$$;
- ($$$3$$$, $$$9$$$, $$$7$$$) — сумма $$$19$$$;
- ($$$4$$$, $$$8$$$, $$$6$$$) — сумма $$$18$$$;
- ($$$9$$$, $$$7$$$, $$$1$$$) — сумма $$$17$$$;
- ($$$8$$$, $$$6$$$, $$$5$$$) — сумма $$$19$$$;
- ($$$7$$$, $$$1$$$, $$$10$$$) — сумма $$$18$$$.
Максимальное количество перевезенных пассажиров достигается на сменах, начатых во $$$2$$$-й и $$$5$$$-й моменты времени.
Во втором наборе входных данных существуют только $$$4$$$ возможные смены из $$$k = 3$$$ маршрутов с продолжительностью $$$d = 3$$$:
- ($$$1$$$, $$$1$$$, $$$1$$$) — сумма $$$3$$$;
- ($$$1$$$, $$$1$$$, $$$1$$$) — сумма $$$3$$$;
- ($$$1000000000$$$, $$$1000000000$$$, $$$1000000000$$$) — сумма $$$3000000000$$$;
- ($$$1$$$, $$$1$$$, $$$1$$$) — сумма $$$3$$$.
Максимальное количество людей будет перевезено за смену $$$3$$$ и только за неё.