每场比赛都应该有至少一道求最值的题目。——《鲁迅说的》

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，以及一个整数 $m$，你需要从 $a$ 中选出一个长度为 $m$ 的子序列，$a_{b_1},a_{b_2},\cdots,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(l,r)$ 定义为 $\min(a_l,a_{l+1},\cdots,a_r)$。

请你求出所有子序列的权值的最大值。

输入格式

第一行两个整数，表示 $n$ 和 $m$。

接下来一行 $n$ 个整数 $a_1 \sim a_n$。

输出格式

一行一个整数，表示答案。

样例输入1

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

样例输出1

176

数据范围

对于 20% 的数据，$n\le 18$；

对于 40% 的数据，$n\le 100$；

对于 60% 的数据，$n\le 500$；

对于 100% 的数据，$n\le 5000,1\le m\le n,1\le a_i< 2^{31}$。