Subsequence

题意翻译

$Alice$ 有一个长度为 $n$ 的整数序列 $a$，所有元素都是不同的。她将选择一个长度为 $m$ 的 $a$ 的子序列，并将一个子序列 $a_{b1},a_{b2},...,a_{bm}$ 的价值定义为 $\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j))$ 其中 $f(i,j)$ 表示 $min(a_i,a_{i+1},..., a_j)$ 。 $Alice$ 希望你能帮助她将她所选择的子序列的价值最大化。 如果一个序列 $s$ 可以通过删除序列 $t$ 中几个元素（可以不删除任何元素或删除全部元素）得到，那么这个序列 $s$ 就是序列 $t$ 的一个子序列。 ### 输入格式 第一行包含两个整数 $n$ 和 $m\ (1≤m≤n≤4000)$。 第二行包含 $n$ 个不同的整数 $a_1,a_2,...,a_n\ (1≤a_i<2^{31})$。 ### 输出格式 输出 $Alice$ 能够得到的最大子序列价值 ### 样例解释 在第一个例子中，$Alice$ 可以选择子序列 $[15, 2, 18, 13]$ , 该子序列的值为 $4 \cdot (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100$。 在第二个例子中，有多种价值为 $176$ 的子序列，其中一个是 $[9，7，12，20，18]$。

题目描述

Alice has an integer sequence $ a $ of length $ n $ and all elements are different. She will choose a subsequence of $ a $ of length $ m $ , and defines the value of a subsequence $ a_{b_1},a_{b_2},\ldots,a_{b_m} $ as $ $\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j)), $ $ where $ f(i, j) $ denotes $ \\min(a\_i, a\_{i + 1}, \\ldots, a\_j) $ .</p><p>Alice wants you to help her to maximize the value of the subsequence she choose.</p><p>A sequence $ s $ is a subsequence of a sequence $ t $ if $ s $ can be obtained from $ t$ by deletion of several (possibly, zero or all) elements.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le m \le n \le 4000 $ ). The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i < 2^{31} $ ).

输出格式

Print the maximal value Alice can get.

输入输出样例

输入样例 #1

6 4
15 2 18 12 13 4

输出样例 #1

100

输入样例 #2

11 5
9 3 7 1 8 12 10 20 15 18 5

输出样例 #2

176

输入样例 #3

1 1
114514

输出样例 #3

0

输入样例 #4

2 1
666 888

输出样例 #4

0

说明

In the first example, Alice can choose the subsequence $ [15, 2, 18, 13] $ , which has the value $ 4 \cdot (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100 $ . In the second example, there are a variety of subsequences with value $ 176 $ , and one of them is $ [9, 7, 12, 20, 18] $ .