题目描述

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

長さ $M$ の $A$ の連続部分列 $B=(B_1,B_2,\dots,B_M)$ に対する、$\displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i$ の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力せよ。

题目大意

对于长度为 $N$ 的数组 $a$ ，求出它所有连续的长度是 $M$ 的子数组 $b$ 的 $\displaystyle\ \sum_{i=1}^{M}\ i\ \times\ b_i$ 的最大值。

4 2
5 4 -1 8

15

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

31

提示

注記

数列の連続部分列とは、数列の先頭から $0$ 個以上、末尾から $0$ 個以上の要素を削除して得られる列のことをいいます。

例えば $(2,\ 3)$ や $(1,\ 2,\ 3)$ は $(1,\ 2,\ 3,\ 4)$ の連続部分列ですが、$(1,\ 3)$ や $(3,2,1)$ は $(1,\ 2,\ 3,\ 4)$ の連続部分列ではありません。

制約

• $1\ \le\ M\ \le\ N\ \le\ 2\ \times\ 10^5$
• $ -\ 2\ \times\ 10^5\ \le\ A_i\ \le\ 2\ \times\ 10^5 $
• 入力は全て整数。

Sample Explanation 1

$B=(A_3,A_4)$ とした場合、$ \displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i\ =\ 1\ \times\ (-1)\ +\ 2\ \times\ 8\ =\ 15 $ となります。$16$ 以上の値を達成することはできないため、解は $15$ です。 $B=(A_1,A_4)$ などを選ぶことができないことに注意してください。