#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
struct modint {
  long long x;
  modint(long long o = 0) { x = o; }
  modint &operator=(long long o) { return x = o, *this; }
  modint &operator+=(modint o) {
    return x = x + o.x >= 1000000007 ? x + o.x - 1000000007 : x + o.x, *this;
  }
  modint &operator-=(modint o) {
    return x = x - o.x < 0 ? x - o.x + 1000000007 : x - o.x, *this;
  }
  modint &operator*=(modint o) { return x = 1ll * x * o.x % 1000000007, *this; }
  modint &operator^=(long long b) {
    modint a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint &operator/=(modint o) { return *this *= o ^= 1000000007 - 2; }
  modint &operator+=(long long o) {
    return x = x + o >= 1000000007 ? x + o - 1000000007 : x + o, *this;
  }
  modint &operator-=(long long o) {
    return x = x - o < 0 ? x - o + 1000000007 : x - o, *this;
  }
  modint &operator*=(long long o) {
    return x = 1ll * x * o % 1000000007, *this;
  }
  modint &operator/=(long long o) {
    return *this *= ((modint(o)) ^= 1000000007 - 2);
  }
  template <class I>
  friend modint operator+(modint a, I b) {
    return a += b;
  }
  template <class I>
  friend modint operator-(modint a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint operator*(modint a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint operator/(modint a, I b) {
    return a /= b;
  }
  friend modint operator^(modint a, long long b) { return a ^= b; }
  friend bool operator==(modint a, long long b) { return a.x == b; }
  friend bool operator!=(modint a, long long b) { return a.x != b; }
  bool operator!() { return !x; }
  modint operator-() { return x ? 1000000007 - x : 0; }
};
vector<modint> fac, ifac, iv;
inline void initC(long long n) {
  if (iv.empty()) fac = ifac = iv = vector<modint>(2, 1);
  long long m = iv.size();
  ++n;
  if (m >= n) return;
  iv.resize(n), fac.resize(n), ifac.resize(n);
  for (register long long i = (m); i <= (n - 1); ++i) {
    iv[i] = iv[1000000007 % i] * (1000000007 - 1000000007 / i);
    fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * iv[i];
  }
}
inline modint C(long long n, long long m) {
  if (m < 0 || n < m) return 0;
  return initC(n), fac[n] * ifac[m] * ifac[n - m];
}
inline modint sign(long long n) { return (n & 1) ? (1000000007 - 1) : (1); }
long long n, m, sz[5005];
long long f[5005][5005], a[5005];
long long solve(long long l, long long r) {
  if (l > r) return 0;
  long long p = l;
  for (register long long i = (l + 1); i <= (r); ++i)
    if (a[i] < a[p]) p = i;
  long long ls = solve(l, p - 1), rs = solve(p + 1, r);
  sz[p] = sz[ls] + sz[rs] + 1;
  for (register long long i = (0); i <= (sz[ls]); ++i)
    for (register long long j = (0); j <= (sz[rs]); ++j) {
      f[p][i + j] = max(f[p][i + j], f[ls][i] + f[rs][j] - a[p] * (i * j * 2));
      f[p][i + j + 1] =
          max(f[p][i + j + 1],
              f[ls][i] + f[rs][j] + (m - 2 * (i + 1) * (j + 1) + 1) * a[p]);
    }
  return p;
}
signed main() {
  n = read(), m = read();
  for (register long long i = (1); i <= (n); ++i) a[i] = read();
  cout << f[solve(1, n)][m];
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
struct modint {
  long long x;
  modint(long long o = 0) { x = o; }
  modint &operator=(long long o) { return x = o, *this; }
  modint &operator+=(modint o) {
    return x = x + o.x >= 1000000007 ? x + o.x - 1000000007 : x + o.x, *this;
  }
  modint &operator-=(modint o) {
    return x = x - o.x < 0 ? x - o.x + 1000000007 : x - o.x, *this;
  }
  modint &operator*=(modint o) { return x = 1ll * x * o.x % 1000000007, *this; }
  modint &operator^=(long long b) {
    modint a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint &operator/=(modint o) { return *this *= o ^= 1000000007 - 2; }
  modint &operator+=(long long o) {
    return x = x + o >= 1000000007 ? x + o - 1000000007 : x + o, *this;
  }
  modint &operator-=(long long o) {
    return x = x - o < 0 ? x - o + 1000000007 : x - o, *this;
  }
  modint &operator*=(long long o) {
    return x = 1ll * x * o % 1000000007, *this;
  }
  modint &operator/=(long long o) {
    return *this *= ((modint(o)) ^= 1000000007 - 2);
  }
  template <class I>
  friend modint operator+(modint a, I b) {
    return a += b;
  }
  template <class I>
  friend modint operator-(modint a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint operator*(modint a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint operator/(modint a, I b) {
    return a /= b;
  }
  friend modint operator^(modint a, long long b) { return a ^= b; }
  friend bool operator==(modint a, long long b) { return a.x == b; }
  friend bool operator!=(modint a, long long b) { return a.x != b; }
  bool operator!() { return !x; }
  modint operator-() { return x ? 1000000007 - x : 0; }
};
vector<modint> fac, ifac, iv;
inline void initC(long long n) {
  if (iv.empty()) fac = ifac = iv = vector<modint>(2, 1);
  long long m = iv.size();
  ++n;
  if (m >= n) return;
  iv.resize(n), fac.resize(n), ifac.resize(n);
  for (register long long i = (m); i <= (n - 1); ++i) {
    iv[i] = iv[1000000007 % i] * (1000000007 - 1000000007 / i);
    fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * iv[i];
  }
}
inline modint C(long long n, long long m) {
  if (m < 0 || n < m) return 0;
  return initC(n), fac[n] * ifac[m] * ifac[n - m];
}
inline modint sign(long long n) { return (n & 1) ? (1000000007 - 1) : (1); }
long long n, m, sz[5005];
long long f[5005][5005], a[5005];
long long solve(long long l, long long r) {
  if (l > r) return 0;
  long long p = l;
  for (register long long i = (l + 1); i <= (r); ++i)
    if (a[i] < a[p]) p = i;
  long long ls = solve(l, p - 1), rs = solve(p + 1, r);
  sz[p] = sz[ls] + sz[rs] + 1;
  for (register long long i = (0); i <= (sz[ls]); ++i)
    for (register long long j = (0); j <= (sz[rs]); ++j) {
      f[p][i + j] = max(f[p][i + j], f[ls][i] + f[rs][j] - a[p] * (i * j * 2));
      f[p][i + j + 1] =
          max(f[p][i + j + 1],
              f[ls][i] + f[rs][j] + (m - 2 * (i + 1) * (j + 1) + 1) * a[p]);
    }
  return p;
}
signed main() {
  n = read(), m = read();
  for (register long long i = (1); i <= (n); ++i) a[i] = read();
  cout << f[solve(1, n)][m];
  return 0;
}

```