最大子段和 II

题目描述

给定一个长度为 n 的数列 A = {$a_1$, $a_2$, ……，$a_n$}。请你在数列 A 中选取长度为 m 的连续子段，并按照从左到右的顺序依次存入数组 b 中（从下标 1 开始存储）。请问 Σ_{i=1}^m i×$b_i$ 的最大值是多少？

其中，Σ_{i=1}^m i×$b_i$ 等价于 1×b_1 + 2×b_2 + …… + i×b_i + …… + m×b_m。

输入描述

第一行包含两个整数 n、m。

第二行包含 n 个整数 $a_1$、$a_2$、……、$a_n$。

输出描述

一行一个整数，表示答案。

样例 1

输入：

4 2
5 4 -1 8

输出：

15

样例 1 解释：数组 b 为 [a_3, a_4] 时，Σ i×$b_i$ = 1×(-1)+2×8 = 15，此时子段和最大。

样例 2

输入：

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

输出：

31

样例 3

输入：

5 3
-10 -9 -13 -7 -21

输出：

-56

数据范围

• 对于 50% 的数据保证：1 ≤ n ≤ 5000。
• 对于 100% 的数据保证：1 ≤ m ≤ n ≤ 2×10^5，-10^5 ≤ $a_i$ ≤ 10^5。