题目描述

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

長さ $M$ の $A$ の部分列(連続でなくてもよい) $B=(B_1,B_2,\dots,B_M)$ に対する、$\displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i$ の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力せよ。

题目大意

题目描述

有一个长度为 $N$ 整数数列 $A=(A_1,A_2,...,A_N)$ 。

现在假设有一个长度为 $M$ 的序列 $B$ ,并且 $B$ 是 $A$ 的子序列。请找到 $\sum_{i=1}^M i\times B_i$ 的最大值。

输入格式

输入按照下面的标准格式给出：

$N\ M \newline A_1 \ A_2 \ \dots\ A_N$

输出格式

一个整数，表示$\sum_{i=1}^M i\times B_i$ 的最大值。

说明 / 提示

注意事项

若序列 $S$ 是长度为 $L$ 的数列 $T$ 的子序列，则 $S$ 是数列 $T$ 删除任意 $i\ (i\in [0,L])$ 个元素得到的。

比如说， $(10,30)$ 是 $(10,20,30)$ 的字串，但是 $(20,10)$ 不是。

数据范围

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

样例解释

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

4 2
5 4 -1 8

21

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

54

提示

注記

数列の部分列とは、数列から $0$ 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる数列のことをいいます。

例えば、$(10,30)$ は $(10,20,30)$ の部分列ですが、$(20,10)$ は $(10,20,30)$ の部分列ではありません。

制約

• $1\ \le\ M\ \le\ N\ \le\ 2000$
• $ -\ 2\ \times\ 10^5\ \le\ A_i\ \le\ 2\ \times\ 10^5 $
• 入力は全て整数。

Sample Explanation 1

$B=(A_1,A_4)$ とした場合、$ \displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i\ =\ 1\ \times\ 5\ +\ 2\ \times\ 8\ =\ 21 $ となります。$22$ 以上の値を達成することはできないため、解は $21$ です。