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;
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
class fenw {
 public:
  ;
  int n;
  vector<long long> fen;
  fenw(int _n) : n(_n) { fen.resize(n); }
  void add(int pos, long long val) {
    while (pos < n) {
      fen[pos] += val;
      pos |= (pos + 1);
    }
  }
  long long get(int pos) {
    long long res = 0;
    while (pos >= 0) {
      res += fen[pos];
      pos = ((pos + 1) & pos) - 1;
    }
    return res;
  }
  long long get(int l, int r) { return get(r) - get(l - 1); }
};
struct seg {
  int l = -1, r = -1, id = -1;
  seg(){};
  seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){};
  bool operator<(const seg &a) const {
    return make_pair(l, r) < make_pair(a.l, a.r);
  }
};
int n, k;
int main() {
  scanf("%d%d", &n, &k);
  vector<int> a(n);
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a[i], &b[i]);
  }
  set<seg> res;
  auto add = [&](int l, int r, int id) {
    auto it = res.lower_bound(seg(l, -1, -1));
    if (it != res.begin()) it--;
    auto memo = it;
    seg st, ed;
    vector<pair<long long, long long>> ans;
    vector<seg> er;
    while (it != res.end()) {
      if (it->l < l && it->r > l) {
        st = seg(it->l, l, it->id);
      }
      if (it->l < r && it->r > r) {
        ed = seg(r, it->r, it->id);
      }
      if (it->l >= r) break;
      int _l = max(it->l, l), _r = min(it->r, r);
      if (_l < _r) {
        er.push_back(*it);
        ans.emplace_back(_l - _r, it->id);
      }
      it++;
    }
    if (memo != res.end() && max(memo->l, l) >= min(memo->r, r)) memo++;
    for (auto i : er) res.erase(i);
    if (~st.id) res.insert(st);
    if (~ed.id) res.insert(ed);
    seg foo = seg(l, r, id);
    res.insert(foo);
    ans.emplace_back(r - l, id);
    return ans;
  };
  vector<vector<pair<long long, long long>>> ais;
  for (int i = 0; i < n; i++) ais.push_back(add(a[i], b[i], i));
  int lo = 0, hi = 1e9;
  while (hi - lo > 1) {
    int mid = (hi + lo) >> 1;
    vector<int> dep(n);
    long long cnt = 0;
    res.clear();
    int sum = 0;
    int cur = 0;
    for (int i = 0; i < n; i++) {
      if (i) sum -= dep[i - 1];
      while (sum < mid && cur < n) {
        for (auto j : ais[cur]) {
          if (j.second >= i) sum += j.first;
          dep[j.second] += j.first;
        }
        cur++;
      }
      if (sum >= mid) cnt += n - cur + 1;
    }
    if (cnt >= k)
      lo = mid;
    else
      hi = mid;
  }
  int dis = lo;
  vector<int> dep(n);
  vector<int> to(n);
  res.clear();
  long long ans = 0;
  int cur = n - 1;
  int sum = 0;
  for (int i = n - 1; i > -1; i--) {
    if (i != n - 1) sum -= dep[i + 1];
    while (~cur && sum < dis) {
      auto bar = add(a[cur], b[cur], cur);
      for (auto j : bar) {
        dep[j.second] += j.first;
        if (j.second <= i) sum += j.first;
      }
      cur--;
    }
    if (sum >= dis)
      to[i] = cur + 1;
    else
      to[i] = -1;
  }
  fenw st(n);
  fenw cl(n);
  long long sp = 0;
  for (int i = 0; i < n; i++) sp += to[i] + 1;
  sp -= k;
  for (int i = 0; i < n; i++) {
    for (auto j : ais[i]) {
      st.add(j.second, 1LL * (j.second + 1) * j.first);
      cl.add(j.second, j.first);
    }
    if (~to[i]) ans += st.get(to[i]);
    ans += 1LL * (to[i] + 1) * cl.get(to[i] + 1, i);
  }
  ans -= sp * dis;
  printf("%lld", ans);
  return 0;
}
