题目描述

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

找出长度为 $M$ 的子序列 $B=(B_1,B_2,\dots,B_M)$，使得 $\\displaystyle \\sum_{i=1}^{M} i \times B_i$ 的值最大。

注意事项

一个子序列是从原始数字序列中删除 $0$ 个或多个元素所得到的序列。

例如，$(2, 3)$ 和 $(1, 2, 3)$ 是 $(1, 2, 3, 4)$ 的子序列，但是 $(1, 3)$ 和 $(3,2,1)$ 不是 $(1, 2, 3, 4)$ 的子序列。

约束条件

• $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$。

请注意，例如，你不能选择 $B=(A_1,A_3)$。

示例输入 2

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

示例输出 2

54