#include <bits/stdc++.h>
namespace wxy {
const long long N = 4005, inf = 1ll << 31;
long long f[N][N], tot;
long long a[N], size[N];
long long n, m, ls[N], rs[N];
void calc(long long &u, long long l, long long r) {
  if (!u) u = ++tot;
  long long rt = 0;
  size[u] = 1;
  if (l == r) {
    f[u][1] = (m - 1) * a[l];
    return;
  }
  for (long long i = l; i <= r; i++)
    if (a[rt] > a[i]) rt = i;
  if (rt != l) calc(ls[u], l, rt - 1);
  if (rt != r) calc(rs[u], rt + 1, r);
  for (long long i = 0; i <= std::min(size[ls[u]], m); i++)
    for (long long j = 0; j <= std::min(size[rs[u]], m); j++) {
      if (i + j == 0) continue;
      long long val = f[ls[u]][i] + f[rs[u]][j];
      if (i + j <= m)
        f[u][i + j] = std::max(f[u][i + j], val - 2 * i * j * a[rt]);
      else
        break;
      if (i + j + 1 <= m)
        f[u][i + j + 1] =
            std::max(f[u][i + j + 1], val + m * a[rt] - 2 * i * j * a[rt] -
                                          2 * (i + j) * a[rt] - a[rt]);
    }
  size[u] += size[ls[u]] + size[rs[u]];
}
inline long long get(long long l, long long r) {
  long long res = 0;
  for (long long i = l; i <= r; i++) {
    res += m * a[i];
    for (long long j = l; j <= r; j++) {
      long long val = inf;
      for (long long k = std::min(i, j); k <= std::max(i, j); k++)
        val = std::min(val, a[k]);
      std::cout << val << std::endl;
      res -= val;
    }
  }
  return res;
}
inline void main() {
  memset(f, 0xcf, sizeof f);
  std::cin >> n >> m;
  for (long long i = 1; i <= n; i++) std::cin >> a[i];
  for (long long i = 0; i <= n; i++) f[i][0] = 0;
  a[0] = inf;
  long long rt = 0;
  calc(rt, 1, n);
  std::cout << f[1][m];
}
}  // namespace wxy
signed main() {
  wxy::main();
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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},…,a_{b_m} as $$$∑_{i = 1}^m (m ⋅ a_{b_i}) - ∑_{i = 1}^m ∑_{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)$$$.

Alice wants you to help her to maximize the value of the subsequence she choose.

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.

Input

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 4000).

The second line contains n distinct integers a_1, a_2, …, a_n (1 ≤ a_i < 2^{31}).

Output

Print the maximal value Alice can get.

Examples

Input


6 4
15 2 18 12 13 4


Output


100


Input


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


Output


176


Input


1 1
114514


Output


0


Input


2 1
666 888


Output


0

Note

In the first example, Alice can choose the subsequence [15, 2, 18, 13], which has the value 4 ⋅ (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].

### Response

```cpp
#include <bits/stdc++.h>
namespace wxy {
const long long N = 4005, inf = 1ll << 31;
long long f[N][N], tot;
long long a[N], size[N];
long long n, m, ls[N], rs[N];
void calc(long long &u, long long l, long long r) {
  if (!u) u = ++tot;
  long long rt = 0;
  size[u] = 1;
  if (l == r) {
    f[u][1] = (m - 1) * a[l];
    return;
  }
  for (long long i = l; i <= r; i++)
    if (a[rt] > a[i]) rt = i;
  if (rt != l) calc(ls[u], l, rt - 1);
  if (rt != r) calc(rs[u], rt + 1, r);
  for (long long i = 0; i <= std::min(size[ls[u]], m); i++)
    for (long long j = 0; j <= std::min(size[rs[u]], m); j++) {
      if (i + j == 0) continue;
      long long val = f[ls[u]][i] + f[rs[u]][j];
      if (i + j <= m)
        f[u][i + j] = std::max(f[u][i + j], val - 2 * i * j * a[rt]);
      else
        break;
      if (i + j + 1 <= m)
        f[u][i + j + 1] =
            std::max(f[u][i + j + 1], val + m * a[rt] - 2 * i * j * a[rt] -
                                          2 * (i + j) * a[rt] - a[rt]);
    }
  size[u] += size[ls[u]] + size[rs[u]];
}
inline long long get(long long l, long long r) {
  long long res = 0;
  for (long long i = l; i <= r; i++) {
    res += m * a[i];
    for (long long j = l; j <= r; j++) {
      long long val = inf;
      for (long long k = std::min(i, j); k <= std::max(i, j); k++)
        val = std::min(val, a[k]);
      std::cout << val << std::endl;
      res -= val;
    }
  }
  return res;
}
inline void main() {
  memset(f, 0xcf, sizeof f);
  std::cin >> n >> m;
  for (long long i = 1; i <= n; i++) std::cin >> a[i];
  for (long long i = 0; i <= n; i++) f[i][0] = 0;
  a[0] = inf;
  long long rt = 0;
  calc(rt, 1, n);
  std::cout << f[1][m];
}
}  // namespace wxy
signed main() {
  wxy::main();
  return 0;
}

```