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 N = 100005;
template <class T>
struct BIT {
  int n;
  T bit[N];
  inline void Init(int _n) {
    n = _n;
    for (int i = 1; i <= n; i++) bit[i] = 0;
  }
  inline void add(int i, T x) {
    while (i <= n) {
      bit[i] += x;
      i += i & -i;
    }
  }
  inline T sum(int i) {
    T res = 0;
    while (i > 0) {
      res += bit[i];
      i -= i & -i;
    }
    return res;
  }
};
BIT<int> bit;
BIT<long long> bit2;
struct BIT_MN {
  int n, bit[N];
  inline void Init(int _n) {
    n = _n;
    for (int i = 1; i <= n; i++) bit[i] = 0x3f3f3f3f;
  }
  inline void ins(int i, int x) {
    while (i <= n) {
      bit[i] = min(bit[i], x);
      i += i & -i;
    }
  }
  inline int qry(int i) {
    int res = 0x3f3f3f3f;
    while (i > 0) {
      res = min(res, bit[i]);
      i -= i & -i;
    }
    return res;
  }
} bit_mn;
namespace SegTree {
int lson[N * 20], rson[N * 20], sz[N * 20], tot;
inline void Init() { lson[0] = rson[0] = sz[0] = tot = 0; }
void ins(int &x, int y, int l, int r, int pos) {
  x = ++tot, lson[x] = lson[y], rson[x] = rson[y], sz[x] = sz[y] + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    ins(lson[x], lson[y], l, mid, pos);
  else
    ins(rson[x], rson[y], mid + 1, r, pos);
}
pair<int, int> query(int x, int l, int r, int rnk) {
  if (l == r) return make_pair(l, rnk);
  int mid = (l + r) >> 1;
  if (rnk <= sz[lson[x]])
    return query(lson[x], l, mid, rnk);
  else
    return query(rson[x], mid + 1, r, rnk - sz[lson[x]]);
}
}  // namespace SegTree
int n;
namespace SegTree_minsum {
struct Node {
  long long mn, mx;
} st[N * 4];
inline Node Merge(Node a, Node b) {
  Node c;
  c.mn = min(a.mn, b.mn);
  c.mx = max(a.mx, b.mx);
  return c;
}
void build(int i, int l, int r, long long *a) {
  if (l == r) {
    st[i].mn = st[i].mx = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid, a);
  build(i << 1 | 1, mid + 1, r, a);
  st[i] = Merge(st[i << 1], st[i << 1 | 1]);
}
Node query(int i, int l, int r, int lf, int rg) {
  if (lf <= l && r <= rg) return st[i];
  int mid = (l + r) >> 1;
  if (rg <= mid)
    return query(i << 1, l, mid, lf, rg);
  else if (lf > mid)
    return query(i << 1 | 1, mid + 1, r, lf, rg);
  else
    return Merge(query(i << 1, l, mid, lf, rg),
                 query(i << 1 | 1, mid + 1, r, lf, rg));
}
inline long long query_minsum(int l, int r) {
  Node t = query(1, 1, n, l, r);
  return t.mn - t.mx;
}
}  // namespace SegTree_minsum
using SegTree_minsum::query_minsum;
namespace KTH {
multiset<long long> A, B;
long long sum;
int k;
inline void Init(int _k) {
  k = _k;
  sum = 0;
}
inline void Upd() {
  while ((int)A.size() > k) {
    long long cur = *A.rbegin();
    A.erase(A.find(cur));
    B.insert(cur);
    sum -= cur;
  }
  while ((int)A.size() < k && B.size()) {
    long long cur = *B.begin();
    B.erase(B.find(cur));
    A.insert(cur);
    sum += cur;
  }
}
inline void ins(long long val) {
  A.insert(val);
  sum += val;
  Upd();
}
inline void del(long long val) {
  if (B.find(val) != B.end())
    B.erase(B.find(val));
  else
    A.erase(A.find(val)), sum -= val;
  Upd();
}
inline void Minus() {
  k--;
  Upd();
}
}  // namespace KTH
int a[N], ps_id[N], cur_pos[N], root[N], cov[N], mn_tag[N], cc_tag[N];
long long m, ps[N], max_ps[N], min_ps[N];
vector<int> vs[N];
vector<long long> val_ps;
priority_queue<pair<long long, pair<int, int> > > pq;
set<int> uncov;
int main() {
  scanf("%d%lld", &n, &m);
  ps[0] = 0;
  val_ps.push_back(ps[0]);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    ps[i] = ps[i - 1] + a[i];
    val_ps.push_back(ps[i]);
  }
  sort(val_ps.begin(), val_ps.end());
  val_ps.resize(unique(val_ps.begin(), val_ps.end()) - val_ps.begin());
  for (int i = 0; i <= n; i++) {
    ps_id[i] =
        lower_bound(val_ps.begin(), val_ps.end(), ps[i]) - val_ps.begin() + 1;
  }
  min_ps[0] = ps[0];
  for (int i = 1; i <= n; i++) min_ps[i] = min(min_ps[i - 1], ps[i]);
  max_ps[n] = ps[n];
  for (int i = n - 1; i >= 0; i--) max_ps[i] = max(max_ps[i + 1], ps[i]);
  SegTree_minsum::build(1, 1, n, ps);
  long long ans1 = 0;
  if (m - n > 0) {
    long long lo = -5e9, hi = 5e9;
    while (lo < hi) {
      long long mid = lo + (hi - lo + 1) / 2, sk = 0;
      bit.Init(val_ps.size());
      for (int i = 1; i <= n; i++) {
        bit.add(ps_id[i - 1], 1);
        int j = upper_bound(val_ps.begin(), val_ps.end(), ps[i] - mid) -
                val_ps.begin();
        sk += bit.sum(j);
      }
      if (sk < m - n)
        hi = mid - 1;
      else
        lo = mid;
    }
    long long tk = 0;
    bit.Init(val_ps.size());
    bit2.Init(val_ps.size());
    bit_mn.Init(val_ps.size());
    for (int i = 1; i <= n; i++) {
      bit.add(ps_id[i - 1], 1);
      bit2.add(ps_id[i - 1], ps[i - 1]);
      bit_mn.ins(ps_id[i - 1], i);
      int j = upper_bound(val_ps.begin(), val_ps.end(), ps[i] - lo - 1) -
              val_ps.begin();
      int t = bit.sum(j);
      ans1 += ps[i] * t - bit2.sum(j);
      cur_pos[i] = t;
      tk += t;
      if (t) {
        cov[bit_mn.qry(j)]++;
        cov[i + 1]--;
      }
    }
    for (int i = 1; i <= n; i++) mn_tag[i] = 0x3f3f3f3f, cc_tag[i] = 0;
    for (int i = 1; i <= n && tk < m - n; i++) {
      cc_tag[ps_id[i - 1]]++;
      mn_tag[ps_id[i - 1]] = min(mn_tag[ps_id[i - 1]], i);
      int j = lower_bound(val_ps.begin(), val_ps.end(), ps[i] - lo) -
              val_ps.begin();
      if (j < (int)val_ps.size() && val_ps[j] == ps[i] - lo) {
        int t = min(m - n - tk, (long long)cc_tag[j + 1]);
        ans1 += lo * t;
        cur_pos[i] += t;
        tk += t;
        if (t) {
          cov[mn_tag[j + 1]]++;
          cov[i + 1]--;
        }
      }
    }
    for (int i = 1; i <= n; i++) cov[i] += cov[i - 1];
  } else {
    for (int i = 1; i <= n; i++) cur_pos[i] = 0;
  }
  int lst = -1;
  KTH::Init(min(m, (long long)n) - 1);
  for (int i = 1; i <= n; i++)
    if (!cov[i]) {
      if (lst != -1) {
        KTH::ins(query_minsum(lst, i - 1));
      }
      uncov.insert(i);
      lst = i;
    }
  SegTree::Init();
  root[0] = 0;
  for (int i = 1; i <= n; i++) {
    SegTree::ins(root[i], root[i - 1], 1, val_ps.size(), ps_id[i - 1]);
    vs[ps_id[i - 1]].push_back(i);
    if (cur_pos[i] < i) {
      pair<int, int> P =
          SegTree::query(root[i], 1, val_ps.size(), cur_pos[i] + 1);
      int l = vs[P.first][P.second - 1];
      pq.push(make_pair(ps[i] - ps[l - 1], make_pair(l, i)));
    }
  }
  long long ans2 = 0;
  long long ans = -9223372036854775807ll;
  for (int _ = 0, _e = min(m, (long long)n); _ < _e; _++) {
    int rem = _e - _;
    if (rem <= (int)uncov.size()) {
      long long ans3;
      int x = *uncov.begin(), y = *uncov.rbegin();
      ans3 = max_ps[y] - min_ps[x - 1] - KTH::sum;
      ans = max(ans, ans1 + ans2 + ans3);
    }
    pair<long long, pair<int, int> > P = pq.top();
    pq.pop();
    ans2 += P.first;
    int i = P.second.second;
    cur_pos[i]++;
    if (cur_pos[i] < i) {
      pair<int, int> P =
          SegTree::query(root[i], 1, val_ps.size(), cur_pos[i] + 1);
      int l = vs[P.first][P.second - 1];
      pq.push(make_pair(ps[i] - ps[l - 1], make_pair(l, i)));
    }
    int l = P.second.first;
    int x = -1, y = -1;
    auto it = uncov.lower_bound(l);
    if (it != uncov.begin()) --it, x = *it, ++it;
    vector<int> rmv;
    while (it != uncov.end() && *it <= i) {
      rmv.push_back(*it);
      uncov.erase(it++);
    }
    if (it != uncov.end()) y = *it;
    if (rmv.size()) {
      if (x != -1) KTH::del(query_minsum(x, rmv[0] - 1));
      if (y != -1) KTH::del(query_minsum(rmv.back(), y - 1));
      for (int j = 1; j < (int)rmv.size(); j++)
        KTH::del(query_minsum(rmv[j - 1], rmv[j] - 1));
      if (x != -1 && y != -1) KTH::ins(query_minsum(x, y - 1));
    }
    if (_ == _e - 1) break;
    KTH::Minus();
  }
  if (uncov.empty()) {
    ans = max(ans, ans1 + ans2);
  }
  printf("%lld\n", ans);
  return 0;
}