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 maxn = 3e5 + 10, Big = 1e9 + 10;
pair<int, int> p[maxn];
int arr[2 * maxn], n, C;
int pt[maxn];
vector<pair<int, int> > tdo[maxn];
void prep() {
  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; i++) {
    auto it = mp.upper_bound((pair<int, int>){p[i].first, -1});
    if (it != mp.begin()) --it;
    if (it != mp.end() && (it->first.second <= p[i].first)) ++it;
    while (it != mp.end() && it->first.first < p[i].second) {
      auto sg = *it;
      it = next(it);
      mp.erase(prev(it));
      if (sg.first.first <= p[i].first && p[i].second <= sg.first.second) {
        tdo[i].push_back({sg.second, -arr[p[i].second] + arr[p[i].first]});
        if (sg.first.first != p[i].first)
          mp[{sg.first.first, p[i].first}] = sg.second;
        if (sg.first.second != p[i].second)
          mp[{p[i].second, sg.first.second}] = sg.second;
      } else if (p[i].first <= sg.first.first &&
                 sg.first.second <= p[i].second) {
        tdo[i].push_back(
            {sg.second, -arr[sg.first.second] + arr[sg.first.first]});
      } else if (sg.first.second <= p[i].second) {
        tdo[i].push_back({sg.second, -arr[sg.first.second] + arr[p[i].first]});
        mp[{sg.first.first, p[i].first}] = sg.second;
      } else {
        tdo[i].push_back({sg.second, -arr[p[i].second] + arr[sg.first.first]});
        mp[{p[i].second, sg.first.second}] = sg.second;
      }
    }
    tdo[i].push_back({i, arr[p[i].second] - arr[p[i].first]});
    mp[{p[i].first, p[i].second}] = i;
  }
}
int who[maxn];
long long ANS;
long long calc(int x) {
  memset(who, 0, sizeof who);
  int l = 0;
  long long ans = 0;
  long long sum = 0, tot = 0, sum2 = 0;
  ANS = 0;
  for (int r = 0; r < n; r++) {
    for (pair<int, int> pp : tdo[r]) {
      who[pp.first] += pp.second;
      if (pp.first >= l)
        sum += pp.second, sum2 += 1ll * (pp.first + 1) * pp.second;
      tot += 1ll * (pp.first + 1) * pp.second;
    }
    while (sum >= x) {
      sum -= who[l];
      sum2 -= 1ll * (l + 1) * who[l];
      l++;
    }
    pt[r] = l;
    ans += pt[r];
    ANS += tot - sum2 + 1ll * l * sum;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  cin >> n;
  long long k;
  cin >> k;
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
    arr[C++] = p[i].first;
    arr[C++] = p[i].second;
  }
  sort(arr, arr + C);
  C = unique(arr, arr + C) - arr;
  for (int i = 0; i < n; i++) {
    p[i].first = lower_bound(arr, arr + C, p[i].first) - arr;
    p[i].second = lower_bound(arr, arr + C, p[i].second) - arr;
  }
  prep();
  int l = 0, r = Big;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (calc(mid) >= k)
      l = mid;
    else
      r = mid;
  }
  long long num = calc(r);
  return cout << ANS + 1ll * (k - num) * l << endl, 0;
}
