带权选数 - 代码源竞赛平台

题目描述

蜗蜗有一个长度为 $N$ 的整数序列 $a$。他需要按照原来的相对顺序，恰好选出 $M$ 个数。

如果选出的第 $j$ 个数来自原序列下标 $i$，那么它会为总分贡献 $j\times a_i$。请你求出所有合法选择方案中的最大总分。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出一行一个整数，表示最大总分。

样例

3 2
-1 2 3

8

样例解释

选择原序列中的第 2、第 3 个数时，总分为 $1\times2+2\times3=8$；其他选择方案的总分都不超过 8，因此答案为 8。

数据范围

对于 100% 的数据，保证 $1\le M\le N\le2000$，$-10^9\le a_i\le10^9$。