题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。找出 $A$ 的一个长度为 $M$ 的连续子数组 $B=(B_1,B_2,\dots,B_M)$，使得 $\displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i$的值最大。

请计算并输出这个最大值。

连续子数组是指从原序列中删除 0 个或多个开头元素和 0 个或多个结尾元素后得到的序列。

例如，(2, 3) 和 (1, 2, 3) 是 (1, 2, 3, 4) 的连续子数组，但 (1, 3) 和 (3, 2, 1) 不是。

输入格式

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

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

4 2
5 4 -1 8

输出 #1

15

输入输出样例 #2

输入 #2

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

输出 #2

31

说明/提示

样例 1 解释

当 $B=(A_3,A_4)$ 时，我们有 $\sum_{i=1}^M i\times B_i=1\times (-1) + 2 \times 8=15$。由于不可能得到 $16$ 或更大的值，所以答案是 $15$。

注意，你不能选择例如 $B=(A_1,A_4)$。

数据范围

• $1\ \le\ M\ \le\ N\ \le\ 2\ \times\ 10^5$
• $ -\ 2\ \times\ 10^5\ \le\ A_i\ \le\ 2\ \times\ 10^5 $
• 所有输入均为整数。