问题描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

请你求出对于 $A$ 的所有长度为 $M$ 的连续子序列 $B = (B_1, B_2, \ldots, B_M)$，表达式 $\sum_{i=1}^{M} i \times B_i$ 的最大值。

输入格式

一行，包含整数 $N, M$ 和 $N$ 个整数 $A_1, A_2, \ldots, A_N$，相邻两个数之间用一个空格分隔。

输出格式

一个整数，即所求的最大值。

样例输入 1

4 2 5 4 -1 8

样例输出 1

15

说明：取 $B = (A_3, A_4) = (-1, 8)$，$\sum i \cdot B_i = 1 \times (-1) + 2 \times 8 = 15$。其他连续子序列如 $(5, 4)$ 只能得到 $1 \times 5 + 2 \times 4 = 13$，$(4, -1) = 1 \times 4 + 2 \times (-1) = 2$。最大值为 $15$。

样例输入 2

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

样例输出 2

31

样例输入 3

3 1 5 7 9

样例输出 3

9

说明：$M = 1$ 时直接取最大的单元素 $9$。

评测数据规模

对于所有数据，保证 $1 \le M \le N \le 2 \times 10^5$，$|A_i| \le 2 \times 10^5$。