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;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  write(a);
  putchar('\n');
}
inline void wri(long long a) {
  write(a);
  putchar(' ');
}
const int N = 100005;
const long long sj = 6e9, inf = 9e18;
long long a[N], c[N];
pair<long long, int> q[N << 1];
int n;
inline void change(int pos, long long de) {
  for (int i = pos; i < N; i += i & -i) c[i] += de;
}
inline long long ask(int pos) {
  long long ans = 0;
  for (int i = pos; i; i -= i & -i) ans += c[i];
  return ans;
}
pair<long long, long long> Get(long long x) {
  int qq = 0;
  for (int i = 1; i <= n; i++) {
    q[++qq] = make_pair(a[i - 1], -i);
    q[++qq] = make_pair(a[i] - x, i);
    c[i] = 0;
  }
  long long sum = 0, ans = 0;
  sort(&q[1], &q[qq + 1]);
  for (int i = 1; i <= qq; i++)
    if (q[i].second < 0)
      change(-q[i].second, 1);
    else {
      long long t = ask(q[i].second);
      sum += t;
      ans += t * a[q[i].second];
    }
  for (int i = 1; i <= n; i++) c[i] = 0;
  for (int i = 1; i <= qq; i++)
    if (q[i].second < 0)
      change(-q[i].second, q[i].first);
    else
      ans -= ask(q[i].second);
  return make_pair(sum, ans);
}
pair<long long, long long> dp[N], Dp[N], cf[N];
long long mn[N];
pair<long long, long long> askf(int pos) {
  pos = n - pos;
  pair<long long, long long> ans = make_pair(-inf, 0);
  for (int i = pos; i; i -= i & -i) ans = max(ans, cf[i]);
  return ans;
}
void chf(int pos, pair<long long, long long> de) {
  pos = n - pos;
  for (int i = pos; i <= n; i += i & -i) cf[i] = max(cf[i], de);
}
bool cmp(long long a, long long b) { return a > b; }
pair<long long, long long> get(long long x) {
  for (int i = 1; i <= n; i++) cf[i] = make_pair(-inf, 0);
  chf(0, dp[0]);
  for (int i = 1; i <= n; i++) {
    int pos = lower_bound(&mn[0], &mn[i], a[i] - x, cmp) - mn;
    dp[i] = askf(pos);
    if (pos)
      dp[i] = max(dp[i], make_pair(Dp[pos - 1].first + a[i] - x,
                                   Dp[pos - 1].second + 1));
    if (i < n) chf(i, dp[i]);
    mn[i] = min(mn[i - 1], a[i]);
    Dp[i] = max(Dp[i - 1], make_pair(dp[i].first - mn[i], dp[i].second));
  }
  pair<long long, long long> ttt = Get(x);
  dp[n].first += ttt.second - ttt.first * x;
  dp[n].second += ttt.first;
  return dp[n];
}
int main() {
  n = read();
  long long k = read();
  for (int i = 1; i <= n; i++) a[i] = read() + a[i - 1];
  long long l = -sj, r = sj;
  while (l < r) {
    long long mid = (l + r) >> 1;
    mid++;
    if (get(mid).second >= k)
      l = mid;
    else
      r = mid - 1;
  }
  cout << get(l).first + k * l << endl;
}