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;
template <typename T>
inline void read(T &x) {
  x = 0;
  int f = 1, c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) f = 0, c = getchar();
  while (c > 32) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  !f && (x *= -1);
}
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const long long linf = 1LL * inf * inf;
int n;
long long k;
int a[N];
long long sum[N];
long long ans1, ans2;
template <typename T>
struct BIT {
  T sum[N];
  BIT() { memset(sum, 0, sizeof(sum)); }
  void init() { memset(sum, 0, sizeof(sum)); }
  void upd(int x, T v) {
    for (; x < N; x += x & -x) sum[x] += v;
  }
  T qry(int x) {
    T ans = 0;
    for (; x; x -= x & -x) ans += sum[x];
    return ans;
  }
};
struct BIT0 {
  long long mn[N];
  BIT0() { memset(mn, 0x3f, sizeof(mn)); }
  void init() { memset(mn, 0x3f, sizeof(mn)); }
  void upd(int x, long long v) {
    for (; x < N; x += x & -x) mn[x] = min(mn[x], v);
  }
  long long qry(int x) {
    long long ans = linf;
    for (; x; x -= x & -x) ans = min(ans, mn[x]);
    return ans;
  }
};
vector<long long> vx;
int F(long long x) { return upper_bound(vx.begin(), vx.end(), x) - vx.begin(); }
BIT<int> bit;
BIT<long long> bit1;
BIT0 bit0;
long long check(long long S) {
  bit.init();
  long long ans = 0;
  bit.upd(F(0), 1);
  for (int i = 1; i <= n; ++i) {
    ans += bit.qry(F(sum[i] - S));
    bit.upd(F(sum[i]), 1);
  }
  return ans;
}
int cover[N];
void fill(long long S) {
  bit.init();
  bit1.init();
  bit0.init();
  bit.upd(F(0), 1);
  bit1.upd(F(0), 0);
  bit0.upd(F(0), 0);
  for (int i = 1; i <= n; ++i) {
    ans1 += bit.qry(F(sum[i] - S)) * sum[i] - bit1.qry(F(sum[i] - S));
    long long l = bit0.qry(F(sum[i] - S));
    if (l <= i) {
      cover[l + 1]++;
      cover[i + 1]--;
    }
    bit.upd(F(sum[i]), 1);
    bit1.upd(F(sum[i]), sum[i]);
    bit0.upd(F(sum[i]), i);
  }
}
vector<pair<int, int> > rem;
vector<int> occ[N];
set<int> nempty;
void get(long long Sl, long long Sr) {
  for (int i = 0; i <= vx.size(); ++i) occ[i].clear();
  nempty.insert(F(0));
  occ[F(0)].push_back(0);
  for (int i = 1; i <= n; ++i) {
    int l = F(sum[i] - Sr - 1) + 1, r = F(sum[i] - Sl);
    set<int>::iterator it = nempty.lower_bound(l);
    while (it != nempty.end() && *it <= r) {
      int j = *it;
      for (int l = 0; l < occ[j].size(); ++l)
        rem.push_back(make_pair(occ[j][l] + 1, i));
      ++it;
    }
    nempty.insert(F(sum[i]));
    occ[F(sum[i])].push_back(i);
  }
}
void fill_corner(long long S, long long cnt) {
  for (int i = 0; i <= vx.size(); ++i) occ[i].clear();
  ans1 += S * cnt;
  occ[F(0)].push_back(0);
  for (int i = 1; i <= n; ++i) {
    vector<int> &v = occ[F(sum[i] - S)];
    if (!v.empty() && sum[i] - sum[v[0]] == S) {
      if (v.size() >= cnt) {
        for (int j = 0; j < v.size() - cnt && rem.size() < k - max(k - n, 0LL);
             ++j)
          rem.push_back(make_pair(v[j] + 1, i));
        if (cnt) {
          cover[v[v.size() - cnt] + 1]++;
          cover[i + 1]--;
        }
        cnt = 0;
      } else {
        cover[v[0] + 1]++;
        cover[i + 1]--;
        cnt -= v.size();
      }
    }
    occ[F(sum[i])].push_back(i);
  }
}
set<int> uncover;
void precalc() {
  for (int i = 0; i <= n; ++i) vx.push_back(sum[i]);
  sort(vx.begin(), vx.end());
  vx.erase(unique(vx.begin(), vx.end()), vx.end());
  long long lb = -linf, rb = linf;
  while (lb < rb) {
    long long md = lb + (rb - lb + 1) / 2;
    if (check(md) >= max(k - n, 0LL))
      lb = md;
    else
      rb = md - 1;
  }
  fill(lb + 1);
  fill_corner(lb, max(k - n, 0LL) - check(lb + 1));
  for (int i = 1; i <= n; ++i) cover[i] += cover[i - 1];
  for (int i = 1; i <= n; ++i)
    if (!cover[i]) uncover.insert(i);
  long long S = lb;
  lb = -linf, rb = S;
  while (lb < rb) {
    long long md = lb + (rb - lb + 1) / 2;
    if (check(md) >= k)
      lb = md;
    else
      rb = md - 1;
  }
  get(lb + 1, S - 1);
  fill_corner(lb, 0);
}
int myrand() { return rand() << 15 | rand(); }
struct Treap {
  long long val[N], sum[N];
  int fix[N], siz[N];
  int lson[N], rson[N];
  int que[N + 5], lb, rb;
  Treap() {
    root = 0;
    val[0] = sum[0] = 0;
    fix[0] = 0;
    siz[0] = 0;
    lson[0] = rson[0] = 0;
    lb = rb = 0;
    for (int i = 1; i < N; ++i) que[rb++] = i;
  }
  int new_node(long long v) {
    int x = que[lb++];
    if (lb == N + 5) lb = 0;
    val[x] = sum[x] = v;
    fix[x] = myrand();
    siz[x] = 1;
    lson[x] = rson[x] = 0;
    return x;
  }
  void del_node(int x) {
    que[rb++] = x;
    if (rb == N + 5) rb = 0;
  }
  void pushup(int x) {
    siz[x] = siz[lson[x]] + 1 + siz[rson[x]];
    sum[x] = sum[lson[x]] + val[x] + sum[rson[x]];
  }
  void split(int x, int k, int &a, int &b) {
    if (!x) {
      a = b = 0;
      return;
    }
    if (siz[lson[x]] + 1 <= k) {
      a = x;
      split(rson[x], k - siz[lson[x]] - 1, rson[a], b);
      pushup(a);
    } else {
      b = x;
      split(lson[x], k, a, lson[b]);
      pushup(b);
    }
  }
  void split0(int x, int v, int &a, int &b) {
    if (!x) {
      a = b = 0;
      return;
    }
    if (val[x] <= v) {
      a = x;
      split0(rson[x], v, rson[a], b);
      pushup(a);
    } else {
      b = x;
      split0(lson[x], v, a, lson[b]);
      pushup(b);
    }
  }
  int merge(int a, int b) {
    if (!a || !b) return a + b;
    if (fix[a] < fix[b]) {
      rson[a] = merge(rson[a], b);
      pushup(a);
      return a;
    } else {
      lson[b] = merge(a, lson[b]);
      pushup(b);
      return b;
    }
  }
  int root;
  void ins(long long x) {
    int a, b;
    split0(root, x, a, b);
    root = merge(merge(a, new_node(x)), b);
  }
  void del(long long x) {
    int a, b, c;
    split0(root, x, b, c);
    split0(b, x - 1, a, b);
    del_node(b);
    b = merge(lson[b], rson[b]);
    root = merge(merge(a, b), c);
  }
  long long kth(int k) {
    if (k > siz[root]) return -linf;
    int a, b;
    split(root, k, a, b);
    long long ans = sum[a];
    root = merge(a, b);
    return ans;
  }
  void dbg(int x) {
    if (!x) return;
    dbg(lson[x]);
    cerr << val[x] << " ";
    dbg(rson[x]);
  }
};
struct ST {
  long long mx[N][18], mn[N][18];
  int ln[N];
  void build(long long *a, int n) {
    for (int i = 2; i <= n + 1; ++i) ln[i] = ln[i >> 1] + 1;
    for (int i = 0; i <= n; ++i) mx[i][0] = mn[i][0] = a[i];
    for (int j = 1; j < 18; ++j)
      for (int i = 0; i + (1 << j) - 1 <= n; ++i) {
        mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
        mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
      }
  }
  long long qry_max(int l, int r) {
    int k = ln[r - l + 1];
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
  }
  long long qry_min(int l, int r) {
    int k = ln[r - l + 1];
    return min(mn[l][k], mn[r - (1 << k) + 1][k]);
  }
  long long qry(int l, int r) {
    if (l > r) return 0;
    return qry_min(l - 1, r - 1) - qry_max(l, r);
  }
};
ST st;
Treap treap;
set<int>::iterator Find(int x) { return uncover.lower_bound(x); }
int Pre(int x) {
  set<int>::iterator i = Find(x);
  if (i == uncover.begin()) return -inf;
  --i;
  return *i;
}
int Suf(int x) {
  set<int>::iterator i = Find(x);
  ++i;
  if (i == uncover.end()) return inf;
  return *i;
}
int Fir() { return *uncover.begin(); }
int Lst() { return *uncover.rbegin(); }
void Del(int x) {
  if (x != Fir()) {
    int y = Pre(x);
    treap.del(st.qry(y, x));
  }
  if (x != Lst()) {
    int y = Suf(x);
    treap.del(st.qry(x, y));
  }
  if (x != Fir() && x != Lst()) {
    int y = Pre(x), z = Suf(x);
    treap.ins(st.qry(y, z));
  }
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  long long sa = sum[a.second] - sum[a.first - 1];
  long long sb = sum[b.second] - sum[b.first - 1];
  if (sa == sb) return a < b;
  return sa > sb;
}
long long pre[N], suf[N];
void solve() {
  set<int>::iterator it;
  st.build(sum, n);
  pre[0] = 0;
  suf[n + 1] = -linf;
  for (int i = 1; i <= n; ++i) pre[i] = min(pre[i - 1], sum[i]);
  for (int i = n; i; --i) suf[i] = max(suf[i + 1], sum[i]);
  if (!uncover.empty()) {
    int lst = -1;
    for (it = uncover.begin(); it != uncover.end(); ++it) {
      if (~lst) treap.ins(st.qry(lst, *it));
      lst = *it;
    }
  }
  ans2 = -linf;
  long long base = 0;
  sort(rem.begin(), rem.end(), cmp);
  for (int x = 0; x <= rem.size() && x + max(k - n, 0LL) <= k; ++x) {
    int q = k - x - max(k - n, 0LL);
    long long cur;
    if (!q) {
      if (uncover.empty())
        cur = 0;
      else
        cur = -linf;
    } else {
      if (uncover.empty())
        cur = -linf;
      else {
        long long w = treap.kth(q - 1);
        if (w <= -linf)
          cur = -linf;
        else
          cur = suf[Lst()] - pre[Fir() - 1] - w;
      }
    }
    ans2 = max(ans2, base + cur);
    if (x == rem.size()) break;
    int l = rem[x].first, r = rem[x].second;
    base += sum[r] - sum[l - 1];
    it = Find(l);
    while (it != uncover.end() && *it <= r) {
      Del(*it);
      set<int>::iterator nit = it;
      ++nit;
      uncover.erase(it);
      it = nit;
    }
  }
}
int main() {
  read(n);
  read(k);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    sum[i] = sum[i - 1] + a[i];
  }
  precalc();
  solve();
  printf("%lld\n", ans1 + ans2);
  return 0;
}