Optimizing the Matrix

The AI that keeps the Matrix running is a complex system, so the Architect decided to try optimizing it.

The system can be modeled as $n$ nodes connected in a sequence. Each node has a special characteristic $w_i$, its computational importance.

The Architect picks one node and spreads its action to $k$ neighboring nodes in each direction. If a direction has fewer than $k$ nodes, the action spreads to all of them. Let $d$ be the total number of nodes the action reaches. Then the computational importance of the chosen node becomes $(1 + d) \cdot w_i$, and the nodes reached by the action get importance $0$.

Help the Architect find the maximum total computational importance of the system that can be obtained by performing this action.

The first line contains two integers $n$ and $k$, the number of computational nodes and the number of nodes the action spreads to in one direction ($1 \le n \le 2 \cdot 10^5$; $0 \le k \le 2 \cdot 10^5$).

The second line contains $n$ positive integers $w_1, w_2, \dots, w_n$ separated by spaces, the computational importance of each node ($1 \le w_i \le 5 \cdot 10^5$).

Print one integer, the maximum total computational importance of the system that can be obtained.