Little D is a friend of Little C who loves intervals very much instead of number "3".

Now he has n intervals on the number axis, the i-th of which is [a_i,b_i].

Only the n intervals can not satisfy him. He defines the value of an interval of intervals [l,r] (1 ≤ l ≤ r ≤ n, l and r are both integers) as the total length of the union of intervals from the l-th to the r-th.

He wants to select exactly k different intervals of intervals such that the sum of their values is maximal. Please help him calculate the maximal sum.

Input

First line contains two integers n and k (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ k ≤ min\{(n(n+1))/(2),10^9\}) — the number of intervals Little D has and the number of intervals of intervals he will select.

Each of the next n lines contains two integers a_i and b_i, the i-th line of the n lines describing the i-th interval (1 ≤ a_i < b_i ≤ 10^9).

Output

Print one integer — the maximal sum of values Little D can get.

Examples

Input

2 1
1 3
2 4


Output

3

Input

3 3
1 4
5 7
3 6


Output

15

Note

For the first example, Little D will select [1,2], the union of the first interval and the second interval is [1,4], whose length is 3.

For the second example, Little D will select [1,2], [2,3] and [1,3], the answer is 5+6+4=15.
#include <bits/stdc++.h>
using namespace std;
struct itv {
  long long l, r, bh;
} a[300000 + 1];
long long n, K, pr, ans;
long long dic[2 * 300000 + 1], pdic, dis[2 * 300000 + 1], pg, ph, acnt,
    len[300000 + 1][2], sr[300000 + 1];
vector<pair<long long, long long> > ve[300000 + 1], fe[300000 + 1];
map<long long, itv> ma;
pair<long long, itv> g[2 * 300000 + 1], h[2 * 300000 + 1];
inline bool cr(itv x, itv y) { return (x.r > y.l && x.l < y.r); }
inline long long qread() {
  long long nans = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') nans = nans * 10 + c - '0', c = getchar();
  return nans;
}
void putin() {
  n = qread(), K = qread();
  for (long long i = 1; i <= n; i++)
    a[i].l = qread(), a[i].r = qread(), a[i].bh = i;
}
void odtadd(itv x, long long nt) {
  itv nx;
  pg = ph = 0;
  map<long long, itv>::iterator ni = ma.lower_bound(x.r);
  if (ni != ma.begin()) ni--;
  while (ni != ma.end() && cr(ni->second, x)) {
    nx = ni->second;
    if (nx.l < x.l && nx.r > x.r) {
      g[++pg] = make_pair(nx.l, (itv){nx.l, x.l, nx.bh}),
      g[++pg] = make_pair(x.r, (itv){x.r, nx.r, nx.bh});
      ve[nx.bh].push_back(make_pair(nt, x.r - x.l));
    } else if (nx.l >= x.l && nx.r <= x.r) {
      ve[nx.bh].push_back(make_pair(nt, nx.r - nx.l));
    } else if (nx.l < x.l) {
      g[++pg] = make_pair(nx.l, (itv){nx.l, x.l, nx.bh});
      ve[nx.bh].push_back(make_pair(nt, nx.r - x.l));
    } else if (nx.r > x.r) {
      g[++pg] = make_pair(x.r, (itv){x.r, nx.r, nx.bh});
      ve[nx.bh].push_back(make_pair(nt, x.r - nx.l));
    }
    h[++ph] = make_pair(nx.l, nx);
    if (ni == ma.begin()) break;
    ni--;
  }
  g[++pg] = make_pair(x.l, x);
  for (long long i = 1; i <= ph; i++) ma.erase(h[i].first);
  for (long long i = 1; i <= pg; i++) ma.insert(g[i]);
}
void ycl() {
  for (long long i = 1; i <= n; i++) {
    odtadd(a[i], i);
    len[i][0] = len[i][1] = a[i].r - a[i].l;
  }
  for (long long i = 1; i <= n; i++) {
    for (long long j = 0; j < ve[i].size(); j++)
      fe[ve[i][j].first].push_back(make_pair(i, ve[i][j].second)), acnt++;
  }
}
bool chk(long long nx) {
  for (long long i = 1; i <= n; i++) len[i][1] = len[i][0];
  long long np = 0, ng = 0, nans = 0;
  for (long long i = 1; i <= n; i++) {
    while (ng < nx && np <= n) {
      np++;
      for (long long j = 0; j < fe[np].size(); j++) {
        if (fe[np][j].first >= i)
          ng -= fe[np][j].second, len[fe[np][j].first][1] -= fe[np][j].second;
      }
      ng += len[np][0];
    }
    nans += (np - i);
    sr[i] = np - 1;
    ng -= len[i][1];
  }
  return n * (n + 1) / 2 - nans >= K;
}
long long efans() {
  long long nl = 0, nr = 999999999999, nmid;
  while (nl != nr) {
    nmid = (nl + nr + 1) / 2;
    if (chk(nmid))
      nl = nmid;
    else
      nr = nmid - 1;
  }
  return nl;
}
pair<long long, long long> cal(long long nx) {
  memset(sr, 0, sizeof(sr));
  for (long long i = 1; i <= n; i++) len[i][1] = len[i][0];
  long long np = 0, ng = 0, nans = 0, aa = 0, na = 0, slen = 0, ss = 0;
  for (long long i = 1; i <= n; i++) {
    na = 0;
    while (ng < nx && np <= n) {
      np++;
      if (np > n) break;
      for (long long j = 0; j < fe[np].size(); j++) {
        if (fe[np][j].first >= i)
          na += fe[np][j].second, ng -= fe[np][j].second,
              len[fe[np][j].first][1] -= fe[np][j].second;
      }
      ng += len[np][0];
    }
    nans += (np - i);
    sr[np] = i;
    ng -= len[i][1];
  }
  ng = 0;
  for (long long i = 1; i <= n; i++)
    sr[i] = max(sr[i], sr[i - 1]), len[i][1] = len[i][0];
  if (nx == 999999999999) {
  }
  for (long long i = 1; i <= n; i++) {
    ng += (i - ss) * len[i][0];
    slen += len[i][0];
    for (long long j = sr[i - 1] + 1; j <= sr[i]; j++) {
      ng -= slen;
      slen -= len[j][1];
      len[j][1] = 0;
      ss++;
    }
    for (long long j = 0; j < fe[i].size(); j++) {
      if (fe[i][j].first > ss)
        len[fe[i][j].first][1] -= fe[i][j].second, slen -= fe[i][j].second,
            ng -= (fe[i][j].first - ss) * fe[i][j].second;
    }
    aa += ng;
  }
  return make_pair(nans, aa);
}
void cal1() {
  long long nl = efans();
  pair<long long, long long> nt = cal(nl);
  ans = cal(999999999999).second -
        (nl * (n * (n + 1) / 2 - K - nt.first) + nt.second);
  cout << ans << endl;
}
signed main() {
  putin();
  ycl();
  cal1();
  return 0;
}
