B. 加权子序列

题目描述

给定一个长度为 $N$ 的整数数列 $A = (A_1, A_2, \dots, A_N)$。 请你找一个 $A$ 的子序列 $B$（不用连续），长度为 $M$，并且最大化 $\sum_{i=1}^{M} i \times B_i$，输出这个最大值。

输入格式

第一行两个整数 $N\ M$ 第二行 $N$ 个整数 $A_1\ A_2\ \dots\ A_N$

输出格式

输出答案

样例

输入样例#1

4 2
5 4 -1 8

输出样例#1

21

样例解释

对于样例一，当 $B = (A_1, A_4)$ 时，$\sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21$。因为不可能达到 $22$ 或者更大的值，所以答案是 $21$。

输入样例#2

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

输出样例#2

54

数据范围与提示

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