题目描述

小蓝是一名股票交易员。他拿到了一份未来 $N$ 个交易日的预测报告，按时间顺序给出，第 $i$ 天的预测涨跌额为 $A_i$（正数代表预计上涨带来的收益，负数代表预计下跌带来的亏损）。

交易所推出了一个特殊的“阶梯杠杆”活动：参与者必须严格按照时间顺序，从这 $N$ 天中恰好选择 $M$ 天进行交易。活动的第 $1$ 笔交易使用 $1$ 倍杠杆，第 $2$ 笔交易使用 $2$ 倍杠杆，……，第 $M$ 笔交易使用 $M$ 倍杠杆。

如果小蓝按时间顺序挑选的交易涨跌额序列为 $B = (B_1, B_2, \dots, B_M)$，那么他的总盈亏为：

小蓝想知道，在必须保持时间顺序且恰好选择 $M$ 天的情况下，他能获得的最大总盈亏是多少。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示预测天数与必须交易的天数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每天的预测涨跌额。

输出格式

一个整数，表示能获得的最大总盈亏 $\sum_{i=1}^M i \times B_i$。

样例

4 2
5 4 -1 8

21

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

54

样例1解释

预测序列为 $(5,\ 4,\ -1,\ 8)$，需要选择 $2$ 天交易。

• 若选择第 $1$ 天和第 $4$ 天，$B = (5,\ 8)$，总盈亏为 $1 \times 5 + 2 \times 8 = 21$。
• 其余选择方式均无法达到 $22$ 或更高，故答案为 $21$。

样例2解释

预测序列为 $(-3,\ 1,\ -4,\ 1,\ -5,\ 9,\ -2,\ 6,\ -5,\ 3)$，需选择 $4$ 天。

一种最优选择为：第 $2$ 天 $(1)$、第 $4$ 天 $(1)$、第 $6$ 天 $(9)$、第 $8$ 天 $(6)$，得到 $B = (1,\ 1,\ 9,\ 6)$，

总盈亏为 $1 \times 1 + 2 \times 1 + 3 \times 9 + 4 \times 6 = 54$。

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$。

对于 $100\%$ 的数据，$1 \le M \le N \le 2000$，$-2 \times 10^5 \le A_i \le 2 \times 10^5$。