Оптимизация Матрицы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Искусственный интеллект, поддерживающий работу Матрицы — сложная система, поэтому Архитектор решил попробовать оптимизировать ее.

Эту систему можно представить в виде $$$n$$$ последовательно соединенных узлов. Каждый узел обладает специальной характеристикой $$$w_i$$$ — вычислительной важностью.

Архитектор хочет выбрать некоторый узел и распространить его действие на $$$k$$$ соседних узлов в одном и в другом направлении. Если в каком-то из направлений узлов меньше чем $$$k$$$, то он распространит его действие на столько узлов, сколько есть. Будем считать, что он распространил действие выбранного узла суммарно на $$$d$$$ узлов. Тогда вычислительная важность выбранного узла станет равна $$$(1 + d) \cdot w_i$$$, а вычислительная важность узлов, на которое распространилось его действие, будет равна $$$0$$$.

Помогите Архитектору Матрицы понять, какую максимальную суммарную вычислительную важность системы можно получить, выполнив указанное действие.

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

В первой строке входных данных дается два целых числа $$$n$$$ и $$$k$$$ — количество вычислительных узлов и то, на сколько узлов распространяется действие выбранного узла с одной стороны ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$; $$$0 \leqslant k \leqslant 2 \cdot 10^5$$$).

Во второй строке через пробел следуют $$$n$$$ положительных чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \leqslant w_i \leqslant 5 \cdot 10^5$$$) — вычислительная важность каждого из узлов.

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

В первой и единственной строке выходных данных выведите одно целое число — максимальную вычислительную важность системы, которую можно получить.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты из условия, а также тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
110 $$$n \leqslant 3$$$первая ошибка
218 $$$n \leqslant 6$$$1первая ошибка
320 $$$k = 0$$$первая ошибка
428 $$$k \leqslant 1000$$$2первая ошибка
524нет1 – 4первая ошибка

Примеры

Входные данные
3 1
1 3 2
Выходные данные
9
Входные данные
5 1
1 5 3 2 4
Выходные данные
21