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;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 300111;
int n, k;
int pl[maxn], pr[maxn];
vector<pair<int, int> > dv[maxn];
void change_seg(int len, int pre, int cur) {
  if (len == 0) return;
  dv[cur].push_back(make_pair(pre + 1, len));
}
void prework() {
  set<pair<int, int> > st;
  st.insert(make_pair(0, 0));
  st.insert(make_pair(2e9, 0));
  for (int i = 1; i <= n; i++) {
    int l = pl[i], r = pr[i], lst = l;
    int cur = -1;
    while (true) {
      set<pair<int, int> >::iterator it = st.lower_bound(make_pair(l, 0));
      if (cur == -1) cur = it->second;
      if (it->first <= r) {
        change_seg(it->first - lst, it->second, i);
        lst = it->first;
        st.erase(it);
      } else {
        change_seg(r - lst, it->second, i);
        st.insert(make_pair(r, i));
        break;
      }
    }
    st.insert(make_pair(l, cur));
  }
}
int dlt[maxn], L;
long long SUM, TOT;
int CUR;
void segadd(int x, int v) {
  dlt[x] += v;
  if (x <= L) {
    CUR += v;
    SUM += 1ll * (L - x + 1) * v;
  }
}
void incL() {
  CUR += dlt[++L];
  SUM += CUR;
}
long long check(int w) {
  memset(dlt, 0, sizeof(dlt));
  L = 1;
  CUR = SUM = TOT = 0;
  long long ret = 0;
  for (int i = 1; i <= n; i++) {
    int sum = 0;
    for (int j = 0; j < dv[i].size(); j++) {
      sum += dv[i][j].second;
      segadd(dv[i][j].first, dv[i][j].second);
    }
    segadd(i + 1, -sum);
    while (L <= i && CUR >= w) incL();
    ret += L - 1;
    TOT += SUM - CUR;
  }
  return ret;
}
int main() {
  n = getnum(), k = getnum();
  for (int i = 1; i <= n; i++) {
    int l, r;
    pl[i] = getnum(), pr[i] = getnum();
  }
  prework();
  int l = 0, r = 1e9 + 10;
  while (l <= r) {
    int m = l + r >> 1;
    if (check(m) < k)
      r = m - 1;
    else
      l = m + 1;
  }
  long long cnt = check(r);
  assert(cnt >= k);
  long long ans = TOT - (cnt - k) * r;
  cout << ans << endl;
  return 0;
}
