题目描述

小高有一个长度为N的整数序列$A=(A_1,A_2,...,A_N)$。他想从中选择M个元素组成一个新的序列$B=(B_1,B_2,...,B_M)$，使得$\sum_{i=1}^{M} i \times B_i$的值最大。你帮小高计算这个最大值。

• B是A的一个子序列。子序列是指从原序列中删除零个或多个元素后，剩余元素保持原有顺序构成的新序列。

例如，(10,30)是(10,20,30)的一个子序列，但(20,10)不是(10,20,30)的子序列。

输入格式

输入从标准输入中给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出所求答案。

样例

4 2
5 4 -1 8

21

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

54

样例1解释

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

数据范围

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

来源

• AtCoder ABC267D