Alice 有一个长度为 $$$n$$$ 的整数序列 $$$a$$$ 并且所有元素都不同。她将选择长度为 $$$m$$$ 的 $$$a$$$ 子序列,并将子序列 $$$a_{b_1},a_{b_2},\ldots,a_{b_m}$$$ 的值定义为 $$$$$$\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}, \ldots, a_j)$$$。
Alice 希望你帮助她最大化她选择的子序列的价值。
如果 $$$s$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$t$$$ 获得,则序列 $$$s$$$ 是序列 $$$t$$$ 的子序列。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 4000$$$)。
第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i < 2^{31}$$$)。
输出
打印 Alice 可以获得的最大值。
示例
输入 #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
注意
在第一个示例中,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]$$$。