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].
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
vector<int> cartesian_tree(vector<int>& v) {
  int n = v.size();
  vector<int> p(n, -1);
  stack<int> s;
  for (int i = 0, t = -1; i < n; i += 1) {
    for (t = -1; not s.empty() and v[s.top()] > v[i]; s.pop()) t = s.top();
    if (not s.empty()) p[i] = s.top();
    if (t != -1) p[t] = i;
    s.push(i);
  }
  return p;
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> v(n);
  for (int& x : v) cin >> x;
  auto p = cartesian_tree(v);
  vector<int> L(n, -1), R(n, -1), size(n);
  vector<vector<LL>> dp(n, vector<LL>(n + 1));
  int r = 0;
  for (int i = 0; i < n; i += 1) {
    cout << i << " " << p[i] << endl;
    if (p[i] != -1) {
      if (p[i] >= i)
        L[p[i]] = i;
      else
        R[p[i]] = i;
    } else
      r = i;
  }
  function<void(int)> dfs = [&](int u) {
    size[u] = 1;
    if (L[u] != -1) {
      dfs(L[u]);
      size[u] += size[L[u]];
    }
    if (R[u] != -1) {
      dfs(R[u]);
      size[u] += size[R[u]];
    }
    for (int i = 1; i <= size[u]; i += 1) dp[u][i] = -1E18;
    dp[u][1] = (LL)m * v[u] - v[u];
    if (L[u] != -1) {
      for (int i = 1; i <= size[L[u]]; i += 1) {
        dp[u][i] = max(dp[u][i], dp[L[u]][i]);
        dp[u][i + 1] = max(dp[u][i + 1],
                           dp[L[u]][i] - (LL)(2 * i + 1) * v[u] + (LL)m * v[u]);
      }
    }
    if (R[u] != -1) {
      for (int i = 1; i <= size[R[u]]; i += 1) {
        dp[u][i] = max(dp[u][i], dp[R[u]][i]);
        dp[u][i + 1] = max(dp[u][i + 1],
                           dp[R[u]][i] - (LL)(2 * i + 1) * v[u] + (LL)m * v[u]);
      }
    }
    if (L[u] != -1 and R[u] != -1) {
      for (int i = 1; i <= size[L[u]]; i += 1)
        for (int j = 1; j <= size[R[u]]; j += 1) {
          dp[u][i + j] = max(dp[u][i + j],
                             dp[L[u]][i] + dp[R[u]][j] - (LL)i * j * 2 * v[u]);
          dp[u][i + j + 1] = max(
              dp[u][i + j + 1], dp[L[u]][i] + dp[R[u]][j] -
                                    (LL)(i * j * 2 + 2 * i + 2 * j + 1) * v[u] +
                                    (LL)m * v[u]);
        }
    }
  };
  dfs(r);
  cout << dp[r][m] << " ";
  return 0;
}
