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];
struct SEG {
  long long val[4 * maxn], prep[4 * maxn];
  int lz[4 * maxn];
  bool lz0[4 * maxn];
  void build(int l = 0, int r = n, int id = 1) {
    lz0[id] = 0;
    lz[id] = -1;
    val[id] = 0;
    prep[id] = 0;
    if (r - l == 1) {
      prep[id] = pt[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, 2 * id);
    build(mid, r, 2 * id + 1);
    prep[id] = prep[2 * id] + prep[2 * id + 1];
  }
  void shift(int l, int r, int id) {
    assert(lz[id] == -1 || lz0[id] == 0);
    if (lz[id] == -1 && lz0[id] == 0) return;
    if (lz0[id]) {
      val[id] = prep[id];
      if (r - l > 1) {
        lz0[2 * id] = lz0[2 * id + 1] = 1;
        lz[2 * id] = lz[2 * id + 1] = -1;
      }
    } else {
      val[id] = 1ll * (r - l) * lz[id];
      if (r - l > 1) {
        lz[2 * id] = lz[id];
        lz[2 * id + 1] = lz[id];
        lz0[2 * id] = lz0[2 * id + 1] = 0;
      }
    }
    lz0[id] = 0;
    lz[id] = -1;
  }
  void mrg(int id) { val[id] = val[2 * id] + val[2 * id + 1]; }
  void add(int f, int s, int x, int l = 0, int r = n, int id = 1) {
    if (f >= s || l >= r) return;
    shift(l, r, id);
    if (s <= l || r <= f) return;
    if (f <= l && r <= s) {
      lz[id] = x;
      shift(l, r, id);
      return;
    }
    int mid = (l + r) >> 1;
    add(f, s, x, l, mid, 2 * id);
    add(f, s, x, mid, r, 2 * id + 1);
    mrg(id);
  }
  void res(int f, int s, int l = 0, int r = n, int id = 1) {
    if (f >= s || l >= r) return;
    shift(l, r, id);
    if (s <= l || r <= f) return;
    if (f <= l && r <= s) {
      lz0[id] = 1;
      shift(l, r, id);
      return;
    }
    int mid = (l + r) >> 1;
    res(f, s, l, mid, 2 * id);
    res(f, s, mid, r, 2 * id + 1);
    mrg(id);
  }
  long long ask() { return val[1]; }
};
SEG seg;
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 calc(int x) {
  memset(who, 0, sizeof who);
  int l = 0;
  long long ans = 0;
  long long sum = 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;
    }
    while (sum >= x) {
      sum -= who[l++];
    }
    pt[r] = l;
    ans += pt[r];
  }
  return ans;
}
vector<int> ad[2 * maxn], rm[2 * maxn];
long long calc2() {
  seg.build();
  for (int i = 0; i < n; i++) {
    ad[p[i].first].push_back(i);
    rm[p[i].second].push_back(i);
  }
  long long ans = 0;
  set<int> st;
  st.insert(n);
  st.insert(-1);
  auto upd = [&](int l, int r) {
    int pos = upper_bound(pt, pt + n, l) - pt;
    seg.res(max(int(0), l), pos);
    seg.add(pos, r, l + 1);
  };
  for (int i = 0; i < C - 1; i++) {
    for (int id : ad[i]) {
      st.insert(id);
      upd(id, *st.upper_bound(id));
    }
    for (int id : rm[i]) {
      st.erase(id);
      upd(*(--st.upper_bound(id)), *st.upper_bound(id));
    }
    ans += 1ll * (arr[i + 1] - arr[i]) * seg.ask();
  }
  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 << calc2() + 1ll * (k - num) * l << endl, 0;
}
