题目描述

小高有一个长度为 $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 \ \dots\ A_N$

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

4 2
5 4 -1 8

输出 #1

21

输入输出样例 #2

输入 #2

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

输出 #2

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$
• 所有输入数据均为整数