Искусственный интеллект, поддерживающий работу Матрицы — сложная система, поэтому Архитектор решил попробовать оптимизировать ее.
Эту систему можно представить в виде $$$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$$$) — вычислительная важность каждого из узлов.
В первой и единственной строке выходных данных выведите одно целое число — максимальную вычислительную важность системы, которую можно получить.
Баллы за каждую подзадачу начисляются только в случае, если все тесты из условия, а также тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | $$$n \leqslant 3$$$ | первая ошибка | |
| 2 | 18 | $$$n \leqslant 6$$$ | 1 | первая ошибка |
| 3 | 20 | $$$k = 0$$$ | первая ошибка | |
| 4 | 28 | $$$k \leqslant 1000$$$ | 2 | первая ошибка |
| 5 | 24 | нет | 1 – 4 | первая ошибка |
3 1 1 3 2
9
5 1 1 5 3 2 4
21