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 N = 600010;
int n, k, l[N], r[N];
vector<pair<int, int> > tmp, arr;
set<pair<int, pair<int, int> > > st;
vector<pair<int, int> > g[N];
int has[N];
int last[N];
long long sum[N];
long long all[N];
int cur[N];
long long Sum = 0;
int All = 0;
int Last = -1;
set<pair<int, pair<int, int> > >::iterator it, itc;
inline void change(int l1, int r1, int l2, int r2, int idx) {
  itc = st.lower_bound(make_pair(l1, make_pair(r1, idx)));
  st.erase(itc);
  st.insert(make_pair(l2, make_pair(r2, idx)));
  Sum -= (long long)(cur[r1 + 1] - cur[l1]) * (idx + 1);
  Sum += (long long)(cur[r2 + 1] - cur[l2]) * (idx + 1);
}
void init() {
  Sum = 0;
  All = 0;
  Last = -1;
  st.clear();
  for (int nl, nr, nidx, i = 0; i < n; i++) {
    it = st.lower_bound(make_pair(l[i], make_pair(0, 0)));
    if (it != st.begin()) it--;
    if (it != st.end() && it->first < l[i] && (it->second.first) >= l[i]) {
      nl = it->first;
      nr = it->second.first;
      nidx = it->second.second;
      change(nl, nr, nl, l[i] - 1, nidx);
      g[i].push_back(make_pair(nidx, cur[nr + 1] - cur[l[i]]));
      if (nr > r[i] && nidx > Last) {
        Sum += (long long)(cur[nr + 1] - cur[r[i] + 1]) * (nidx + 1);
        st.insert(make_pair(r[i] + 1, make_pair(nr, nidx)));
        g[i].back().second = cur[r[i] + 1] - cur[l[i]];
      }
    }
    it = st.lower_bound(make_pair(l[i], make_pair(0, 0)));
    while (it != st.end() && (it->first) <= r[i]) {
      if (it->second.first <= r[i]) {
        nl = it->first;
        nr = it->second.first;
        nidx = it->second.second;
        st.erase(it);
        Sum -= (long long)(cur[nr + 1] - cur[nl]) * (nidx + 1);
        g[i].push_back(make_pair(nidx, cur[nr + 1] - cur[nl]));
      } else {
        nl = it->first;
        nr = it->second.first;
        nidx = it->second.second;
        change(nl, nr, r[i] + 1, nr, nidx);
        g[i].push_back(make_pair(nidx, cur[r[i] + 1] - cur[nl]));
        break;
      }
      it = st.lower_bound(make_pair(l[i], make_pair(0, 0)));
    }
    Sum += (long long)(cur[r[i] + 1] - cur[l[i]]) * (i + 1);
    st.insert(make_pair(l[i], make_pair(r[i], i)));
    all[i] = Sum;
  }
}
void solve(int val) {
  Sum = 0;
  All = 0;
  Last = -1;
  for (int i = 0; i < n; i++) {
    has[i] = cur[r[i] + 1] - cur[l[i]];
    for (int j = 0; j < (int)g[i].size(); j++) {
      has[g[i][j].first] -= g[i][j].second;
      if (g[i][j].first > Last) {
        All -= g[i][j].second;
        Sum -= (long long)g[i][j].second * (g[i][j].first + 1);
      }
    }
    All += has[i];
    Sum += (long long)has[i] * (i + 1);
    while (Last < i && All >= val) {
      Last++;
      All -= has[Last];
      Sum -= (long long)has[Last] * (Last + 1);
    }
    last[i] = Last;
    sum[i] = Sum - (long long)(last[i] + 1) * (long long)All;
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &l[i], &r[i]);
    tmp.push_back(make_pair(l[i], 2));
    tmp.push_back(make_pair(r[i], 1));
    tmp.push_back(make_pair(l[i], 1));
    tmp.push_back(make_pair(r[i], 2));
  }
  sort(tmp.begin(), tmp.end());
  tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
  for (int i = 0; i < (int)tmp.size() - 1; i++) {
    if (tmp[i].second == 1) continue;
    arr.push_back(make_pair(tmp[i].first, tmp[i + 1].first));
  }
  for (int i = 0; i < n; i++) {
    l[i] =
        lower_bound(arr.begin(), arr.end(), make_pair(l[i], 0)) - arr.begin();
    r[i] = lower_bound(arr.begin(), arr.end(), make_pair(r[i], 0)) -
           arr.begin() - 1;
  }
  for (int i = 0; i < (int)arr.size(); i++) {
    cur[i + 1] = cur[i] + arr[i].second - arr[i].first;
  }
  int low = 1, high = 1000000000, mid;
  long long ans = 0, res = 0;
  int tmp = 0;
  init();
  while (high >= low) {
    mid = (low + high) / 2;
    solve(mid);
    tmp = 0;
    res = 0;
    for (int i = 0; i < n; i++) {
      tmp += (last[i] + 1);
      if (tmp > k) break;
      res += all[i] - sum[i];
    }
    if (tmp <= k) {
      res += (long long)(k - tmp) * (mid - 1);
      ans = res;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  cout << ans << endl;
  return 0;
}
