子序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的整数序列 $a$，其中所有元素互不相同。你需要选择一个长度为 $m$ 的子序列 $a_{b_1},a_{b_2},\ldots,a_{b_m}$，其中 $b_1<b_2<\cdots<b_m$。

定义

$$f(i,j)=\min_{i\le k\le j}a_k.$$

所选子序列的价值为

$$\sum_{i=1}^{m}m a_{b_i}-\sum_{i=1}^{m}\sum_{j=1}^{m}f(\min(b_i,b_j),\max(b_i,b_j)).$$

求价值的最大值。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示所选子序列价值的最大值。

样例输入 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

数据范围

$1\le m\le n\le4000$，$1\le a_i<2^{31}$，且所有 $a_i$ 互不相同。

子任务编号	分值	特殊限制
1	20	$n\le20$
2		$m=2$
3		$a_1<a_2<\cdots<a_n$
4	40	无特殊限制

说明

答案可能超过 $32$ 位有符号整数范围。