28611번 - Оптимизация Матрицы 다국어

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

Эту систему можно представить в виде $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$) --- вычислительная важность каждого из узлов.

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