102673: [AtCoder]ABC267 D - Index × A(Not Continuous ver.)

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Find the maximum value of $\displaystyle \sum_{i=1}^{M} i \times B_i$ for a (not necessarily contiguous) subsequence $B=(B_1,B_2,\dots,B_M)$ of length $M$ of $A$.

Notes

A subsequence of a number sequence is a sequence that is obtained by removing $0$ or more elements from the original number sequence and concatenating the remaining elements without changing the order.

For example, $(10,30)$ is a subsequence of $(10,20,30)$, but $(20,10)$ is not a subsequence of $(10,20,30)$.

Constraints

• $1 \le M \le N \le 2000$
• $- 2 \times 10^5 \le A_i \le 2 \times 10^5$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

21

When $B=(A_1,A_4)$, we have $\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21$. Since it is impossible to achieve $22$ or a larger value, the solution is $21$.

Sample Input 2

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

Sample Output 2

54

问题描述

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。

找到 $A$ 的一个长度为 $M$ 的（不一定连续的）子序列 $B=(B_1,B_2,\dots,B_M)$，使得 $\displaystyle \sum_{i=1}^{M} i \times B_i$ 的值最大。

注释

一个数列的 子序列 是从原始数列中删除 $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$
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

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

输出

打印答案。

样例输入 1

4 2
5 4 -1 8

样例输出 1

21

当 $B=(A_1,A_4)$ 时，我们有 $\displaystyle \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