Problem: Misha has an array of integers of length n. He wants to choose k different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays.

Misha wants to choose the subarrays in such a way that if he calculated the sum of elements for each subarray, and then add up all these sums, the resulting value was maximum possible.

Input

The first line of input contains two integers: n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — the number of elements in the array and the number of different subarrays that must be chosen.

The second line contains n integers ai ( - 50 000 ≤ ai ≤ 50 000) — the elements of the array.

Output

Output one integer — the maximum possible value Misha can get by choosing k different subarrays.

Example

Input

5 4
6 -4 -10 -4 7


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 1e5 + 5;
const long long INF = 1e18;
int n;
int a[N];
long long pre[N];
struct element {
  long long sum, tot;
  element(const long long sum_ = 0, const long long tot_ = 0) {
    sum = sum_;
    tot = tot_;
  }
  friend element operator+(element a, element b) {
    return element(a.sum + b.sum, a.tot + b.tot);
  }
  friend bool operator>(element a, element b) {
    return a.sum != b.sum ? a.sum > b.sum : a.tot < b.tot;
  }
};
int R[N];
bool bz[N];
struct section {
  int l, r;
  section(const int l_ = 0, const int r_ = 0) {
    l = l_;
    r = r_;
  }
} s[N];
long long mi[N][20], mx[N][20];
long long getmx(int l, int r) {
  long long ret = -INF;
  if (l < 1) ret = 0, l++;
  if (l <= r) {
    int t = log(r - l + 1) / log(2);
    ret = max(ret, max(mx[l][t], mx[r - (1 << t) + 1][t]));
  }
  return ret;
}
long long getmi(int l, int r) {
  long long ret = INF;
  if (l < 1) ret = 0, l++;
  if (l <= r) {
    int t = log(r - l + 1) / log(2);
    ret = min(ret, min(mi[l][t], mi[r - (1 << t) + 1][t]));
  }
  return ret;
}
element f[N];
struct node {
  long long sum;
  int tot, mx, l, r;
} tree[N * 20];
int rt[N], tot;
long long key[N];
int num[N], rk[N];
void add(int &now, int qf, int l, int r, int x) {
  tree[now = ++tot] = tree[qf];
  tree[now].tot = tree[now].tot + 1;
  tree[now].mx = max(tree[now].mx, num[x]);
  tree[now].sum = tree[now].sum + key[x];
  if (l == r) return;
  int mid = (l + r) / 2;
  if (x <= mid)
    add(tree[now].l, tree[qf].l, l, mid, x);
  else
    add(tree[now].r, tree[qf].r, mid + 1, r, x);
}
int Mx, Tot;
long long Sum;
void query(int now, int l, int r, long long v) {
  if (!now || key[r] <= v) return;
  if (key[l] > v) {
    Mx = max(Mx, tree[now].mx);
    Tot += tree[now].tot;
    Sum += tree[now].sum;
    return;
  }
  if (l == r) return;
  int mid = (l + r) / 2;
  if (v < key[mid]) query(tree[now].l, l, mid, v);
  query(tree[now].r, mid + 1, r, v);
}
element solve(long long d) {
  element ret = element();
  for (int i = 1; i <= n; i++) R[i] = 0;
  for (int i = n; i >= 1; i--) {
    Mx = Tot = Sum = 0;
    query(rt[i], 1, n, pre[i - 1] - d);
    R[i] = Mx;
    ret = ret + element(Sum - (pre[i - 1] - d) * Tot, Tot);
  }
  for (int i = 1; i <= n; i++) bz[i] = 0;
  int w = 0;
  for (int i = 1; i <= n; i++)
    if (R[i] > w) {
      w = max(w, i - 1);
      for (; w < R[i];) bz[++w] = 1;
    }
  int k = 0;
  if (!bz[1]) s[++k] = section(1, 0);
  for (int i = 1; i <= n; i++)
    if (bz[i]) {
      if (i == 1 || !bz[i - 1]) s[++k] = section(i, 0);
      if (i == n || !bz[i + 1]) s[k].r = i;
    } else if (i > 1 && !bz[i - 1])
      s[++k] = section(i + 1, i);
  if (!bz[n]) s[++k] = section(n + 1, n);
  if (k == 1) return ret;
  element p = element(-INF, 0);
  for (int i = 1; i <= k; i++) {
    if (i == 1)
      f[i] = element(0, 0);
    else
      f[i] = p + element(getmx(s[i].l - 1, s[i].r) + d, 1);
    element t = f[i] + element(-getmi(s[i].l - 1, s[i].r), 0);
    if (t > p) p = t;
  }
  return ret + f[k];
}
bool cmp(int x, int y) { return pre[x] < pre[y]; }
int main() {
  n = get();
  long long K;
  cin >> K;
  for (int i = 1; i <= n; i++) a[num[i] = i] = get();
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
  sort(num + 1, num + 1 + n, cmp);
  for (int i = 1; i <= n; i++) rk[num[i]] = i, key[i] = pre[num[i]];
  for (int i = n; i >= 1; i--) add(rt[i], rt[i + 1], 1, n, rk[i]);
  for (int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = pre[i];
  for (int j = 1; j <= log(n) / log(2); j++)
    for (int i = 1; i <= n - (1 << j) + 1; i++) {
      mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
      mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    }
  long long l = -1e15, r = 1e15;
  element ans;
  long long d;
  while (l <= r) {
    long long mid = (l + r) / 2;
    element u = solve(mid);
    if (u.tot <= K)
      l = mid + 1, ans = u, d = mid;
    else
      r = mid - 1;
  }
  long long Ans = ans.sum - d * K;
  cout << Ans << endl;
  return 0;
}