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;
const int maxn = 100005;
int n, sz, len, cnt, lim;
int a[maxn], psum[maxn], cov[maxn];
pair<int, int> dat[maxn];
long long k, ans, ans2 = -(long long)(1e18), sval, base;
long long sum[maxn];
vector<long long> num;
set<int> pos;
set<pair<long long, int> >::iterator cur;
set<pair<long long, int> > fsum, val;
bool cmp(pair<int, int> a, pair<int, int> b) {
  return sum[a.second] - sum[a.first - 1] > sum[b.second] - sum[b.first - 1];
}
void ins(pair<long long, int> x) {
  x.first = -x.first;
  val.insert(x);
  if (lim == 0) return;
  if (cnt < lim) {
    sval += -x.first;
    cur = --val.end();
    cnt++;
  } else if (x < (*cur)) {
    sval -= -(*cur).first;
    sval += -x.first;
    val.insert(x);
    cur--;
  }
}
void del(pair<long long, int> x) {
  x.first = -x.first;
  if (cnt > 0 && x <= (*cur)) {
    cur++;
    if (cur != val.end()) sval += -(*cur).first, cnt++;
    val.erase(val.find(x));
    sval -= -x.first;
    cnt--;
    if (cur == val.end() && !val.empty()) cur = --val.end();
  } else
    val.erase(val.find(x));
}
namespace ST {
const int mlog = 20;
int lg2[maxn];
long long mn[maxn][mlog], mx[maxn][mlog];
void build() {
  for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 0; i <= n; i++) mn[i][0] = mx[i][0] = sum[i];
  for (int j = 1; j < mlog; j++)
    for (int i = 0; i <= n; i++) {
      if (i + (1 << j - 1) > n)
        mn[i][j] = (long long)(1e18), mx[i][j] = -(long long)(1e18);
      else {
        mn[i][j] = min(mn[i + (1 << j - 1)][j - 1], mn[i][j - 1]);
        mx[i][j] = max(mx[i + (1 << j - 1)][j - 1], mx[i][j - 1]);
      }
    }
}
long long qry_mn(int l, int r) {
  int len = lg2[r - l + 1];
  return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
long long qry_mx(int l, int r) {
  int len = lg2[r - l + 1];
  return max(mx[l][len], mx[r - (1 << len) + 1][len]);
}
}  // namespace ST
long long getval(int l, int r) {
  return ST::qry_mx(l, r) - ST::qry_mn(l - 1, r - 1);
}
class Fenwick {
 public:
  long long t[maxn];
  void clear() {
    for (int i = 1; i <= sz; i++) t[i] = 0;
  }
  void clear_mn() {
    for (int i = 1; i <= sz; i++) t[i] = n + 1;
  }
  void add(int v, long long val) {
    for (; v <= sz; v += (v & -v)) t[v] += val;
  }
  void add_mn(int v, long long val) {
    for (; v <= sz; v += (v & -v)) t[v] = min(t[v], val);
  }
  long long sum(int v) {
    long long res = 0;
    for (; v; v -= (v & -v)) res += t[v];
    return res;
  }
  long long sum_mn(int v) {
    long long res = n + 1;
    for (; v; v -= (v & -v)) res = min(res, t[v]);
    return res;
  }
} Cnt, Sum, Mn;
long long calc(long long lim) {
  Cnt.clear();
  Cnt.add(psum[0], 1);
  long long res = 0;
  for (int i = 1; i <= n; i++) {
    int pos = upper_bound(num.begin(), num.end(), sum[i] - lim) - num.begin();
    res += Cnt.sum(pos);
    Cnt.add(psum[i], 1);
  }
  return res;
}
int main() {
  scanf("%d%lld", &n, &k);
  num.push_back(0);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum[i] = sum[i - 1] + a[i];
    num.push_back(sum[i]);
  }
  ST::build();
  sort(num.begin(), num.end());
  num.resize(unique(num.begin(), num.end()) - num.begin());
  sz = int(num.size());
  for (int i = 0; i <= n; i++)
    psum[i] = lower_bound(num.begin(), num.end(), sum[i]) - num.begin() + 1;
  long long l1 = -(num[sz - 1] - num[0]) - 1, r1 = num[sz - 1] - num[0] + 1;
  while (r1 - l1 > 1) {
    long long mid1 = l1 + (r1 - l1) / 2;
    long long cur = calc(mid1);
    if (cur < k)
      r1 = mid1;
    else
      l1 = mid1;
  }
  long long l2 = -(num[sz - 1] - num[0]) - 1, r2 = num[sz - 1] - num[0] + 1;
  while (r2 - l2 > 1) {
    long long mid2 = l2 + (r2 - l2) / 2;
    long long cur = calc(mid2);
    if (cur < max(0LL, k - n))
      r2 = mid2;
    else
      l2 = mid2;
  }
  long long tot1 = max(k - n, 0LL) - calc(l2 + 1),
            tot2 = min(k - calc(l1 + 1), k - max(k - n, 0LL));
  Cnt.clear();
  Cnt.add(psum[0], 1);
  Mn.clear_mn();
  Mn.add_mn(psum[0], 0);
  fsum.insert(make_pair(sum[0], 0));
  for (int i = 1; i <= n; i++) {
    int pos =
        upper_bound(num.begin(), num.end(), sum[i] - (l2 + 1)) - num.begin();
    int c = Cnt.sum(pos);
    long long s = Sum.sum(pos);
    int id = Mn.sum_mn(pos);
    int cpos = upper_bound(num.begin(), num.end(), sum[i] - l2) - num.begin();
    int cc = Cnt.sum(cpos);
    long long cs = Sum.sum(cpos);
    int cid = Mn.sum_mn(cpos);
    bool done = false;
    if (tot1 >= cc - c) {
      done = true;
      tot1 -= cc - c;
      if (cid <= i) cov[cid + 1]++, cov[i + 1]--;
      ans += cc * sum[i] - cs;
    } else {
      if (id <= i) cov[id + 1]++, cov[i + 1]--;
      ans += c * sum[i] - s;
    }
    set<pair<long long, int> >::iterator it =
        fsum.lower_bound(make_pair(sum[i] - l2 + done, 0));
    while (it != fsum.end()) {
      if (sum[i] - (*it).first < l1) break;
      if (!done && tot1 && (*it).first == sum[i] - l2) {
        cov[(*it).second + 1]++;
        cov[i + 1]--;
        tot1--;
        ans += sum[i] - (*it).first;
      } else if (sum[i] - (*it).first > l1)
        dat[++len] = make_pair((*it).second + 1, i);
      else if (tot2) {
        dat[++len] = make_pair((*it).second + 1, i);
        tot2--;
      } else
        break;
      it++;
    }
    Cnt.add(psum[i], 1);
    Sum.add(psum[i], sum[i]);
    Mn.add_mn(psum[i], i);
    fsum.insert(make_pair(sum[i], i));
  }
  sort(dat + 1, dat + 1 + len, cmp);
  cur = val.begin();
  lim = len - 1;
  int last = 0;
  for (int i = 1; i <= n; i++) {
    cov[i] += cov[i - 1];
    if (!cov[i]) {
      pos.insert(i);
      if (last) ins(make_pair(getval(last, i), last));
      last = i;
    }
  }
  if (pos.empty()) cnt = -1;
  if (cnt == lim)
    ans2 = max(ans2, sval + (pos.empty() ? 0
                                         : (-ST::qry_mn(0, *pos.begin() - 1) +
                                            ST::qry_mx(*pos.rbegin(), n))));
  for (int i = 1; i <= len; i++) {
    int prv, nxt;
    set<int>::iterator it = pos.lower_bound(dat[i].first), iprv = it;
    if (iprv != pos.begin())
      prv = *(--iprv);
    else
      prv = 0;
    last = prv;
    while (it != pos.end()) {
      if ((*it) > dat[i].second) break;
      if (last) del(make_pair(getval(last, (*it)), last));
      last = (*it);
      pos.erase(it++);
    }
    if (it != pos.end())
      nxt = (*it);
    else
      nxt = n + 1;
    if (last != 0 && nxt != n + 1) del(make_pair(getval(last, nxt), last));
    if (prv != 0 && nxt != n + 1) ins(make_pair(getval(prv, nxt), prv));
    base += sum[dat[i].second] - sum[dat[i].first - 1];
    if (pos.empty()) cnt = -1;
    if (cnt > 0 && cnt == lim) {
      sval -= -(*cur).first;
      cur--;
      cnt--;
    }
    lim--;
    if (cnt == lim)
      ans2 = max(ans2, base + sval +
                           (pos.empty() ? 0
                                        : (-ST::qry_mn(0, *pos.begin() - 1) +
                                           ST::qry_mx(*pos.rbegin(), n))));
  }
  printf("%lld\n", ans + ans2);
  return 0;
}