AT_scpc2026_div1_k.Storing Roll Cake

Coshaman bought a roll cake of length $L$ for the SCSC clubroom. The roll cake consists of $L$ consecutive pieces of length $1$, and the preference value of the $i$-th piece from the left is $V_i$.

Lulu wants to store the roll cake in a refrigerator. However, the clubroom refrigerator cannot store a roll cake of length greater than $K$, so Lulu decided to cut the roll cake into pieces of length at most $K$. Since cutting through a piece would make it ugly, Lulu must cut only between adjacent pieces.

When a roll cake is put into the refrigerator, only the end piece is visible from outside. Since the roll cakes must be put in with a fixed orientation, only the rightmost piece of each cut roll cake is visible. Lulu likes pretty things, so Lulu defines the beauty of storage as the sum of the preference values of the visible pieces.

Cutting a roll cake is hard work, so Lulu wants to store it with large beauty of storage while using little effort. When cutting a roll cake of length $s$ into two roll cakes of lengths $x$ and $y$ ($x+y=s$), the required effort is $x \times y$. If several cuts are made, the effort required for the storage is the sum of the effort required for each cut.

Given $L$, $K$, and the preference values of each roll cake piece, find the maximum possible value of $(\text{beauty of storage}) - (\text{effort required for storage})$.

科沙曼为SCSC俱乐部活动室买了一个长度为 $L$ 的卷蛋糕。该卷蛋糕由 $L$ 个长度均为 $1$ 的连续小块组成，从左往右数第 $i$ 块的偏好值为 $V_i$。

露露想把卷蛋糕存入冰箱。然而，俱乐部活动室的冰箱无法容纳长度超过 $K$ 的卷蛋糕，因此露露决定将卷蛋糕切成若干段，每段长度至多为 $K$。由于在某一块内部切割会使蛋糕外观难看，露露只能在相邻两块之间进行切割。

当卷蛋糕被放入冰箱后，只有最末端的一块能从外部看到。由于卷蛋糕必须以固定朝向放入，因此每一段被切割后的卷蛋糕中，仅有其最右侧的一块是可见的。露露喜欢美观的事物，因此她将“储存美观度”定义为所有可见块的偏好值之和。

切割卷蛋糕是一项费力的工作，因此露露希望在尽可能减少工作量的前提下，使储存美观度最大化。当将一段长度为 $s$ 的卷蛋糕切割成两段长度分别为 $x$ 和 $y$ 的卷蛋糕（满足 $x+y=s$）时，所需的努力值为 $x \times y$。若进行了多次切割，则整个储存过程所需的总努力值等于每次切割所耗费努力值的总和。

给定 $L$、$K$ 以及每一块卷蛋糕的偏好值，求 $(\text{储存美观度}) - (\text{储存所需努力值})$ 的最大可能值。

The input is given from Standard Input in the following format:

$L$ $K$
$V_1$ $V_2$ $\dots$ $V_L$

输入从标准输入中以如下格式给出：

$L$ $K$
$V_1$ $V_2$ $\dots$ $V_L$

Output the maximum possible value of $(\text{beauty of storage}) - (\text{effort required for storage})$.

输出 $(\text{存储的美观度}) - (\text{存储所需的努力})$ 的最大可能值。

表示言語

/ /

Constraints

• $1 \leq K \leq L \leq 1\,000\,000$
• $0 \leq V_i \leq 10^9$
• All given numbers are integers.

表示语言

/ /

限制条件

• $1 \leq K \leq L \leq 1\,000\,000$
• $0 \leq V_i \leq 10^9$
• 所有给定的数均为整数。