说明

在一个正整数数组或子数组中，每个出现的数字乘上它的出现次数，称为它的叠加值。「子数组」是指一个数组中，由连续元素所组成的一部分。例如数组 $[4, 5, 2, 3, 4, 2, 2]$ 中，$5$ 的叠加值是 $5\times1=5$，$4$ 的叠加值是 $4\times2=8$，$3$ 的叠加值是 $3\times1=3$，而 $2$ 的叠加值是 $2\times3=6$。

输入一个长度为 $n$ 的正整数数组以及一个正整数 $k$，本题要求每一个长度为 $k$ 的子数组中的最大叠加值。一共有 $n-k+1$ 个长度为 $k$ 的子数组，输出这 $n-k+1$ 个最大叠加值的总和。

举例来说，输入数组是 $[4, 5, 2, 3, 4, 2, 2, 5]$，$n=8$，$k=5$，各个子数组的最大叠加值如下：

• $[4, 5, 2, 3, 4]$ 的最大叠加值是 $4\times2=8$。
• $[5, 2, 3, 4, 2]$ 的最大叠加值是 $5\times1=5$。
• $[2, 3, 4, 2, 2]$ 的最大叠加值是 $2\times3=6$。
• $[3, 4, 2, 2, 5]$ 的最大叠加值是 $5\times1=5$。

所有最大叠加值的总和是 $8+5+6+5=24$。

输入格式

$$\begin{aligned} &n \; k \\ &c_0 \; c_1 \; \cdots \; c_{n-1} \end{aligned}$$

• $n$ 为数组的长度。
• $k$ 为所要求子数组的长度。
• $c_i$ 为数组中的第 $i$ 个正整数。

输出格式

$X$

• $X$ 为所有叠加最大值的总和。

8 5
4 5 2 3 4 2 2 5

24

提示

数据限制

• $1 \le n\le 10^5$。
• $1 \le k \le n$。
• $1 \le c_i < 2^{31}$。

评分说明

本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	6	输入满足$N \le 1000$， 且$c_i \le 10^6$。
2	38	输入满足数组数字均不相等。
3	56	无额外限制。