說明

在一個正整數陣列或子陣列中，每個出現的數字乘上它的出現次數，稱為它的疊加值。「子陣列」是指一個陣列中，由連續元素所組成的一部分。例如陣列 $[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	無額外限制。