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 std::pair;
using std::set;
using std::vector;
int n, k, a[300005], b[300005], mx, tag[300005];
set<pair<pair<int, int>, int> > st;
vector<pair<pair<int, int>, int> > del, ins;
vector<pair<int, int> > op[300005];
inline void insert(int l, int r, int col) {
  auto it = st.lower_bound(std::make_pair(std::make_pair(l, r), 0));
  int tot = r - l;
  if (it != st.begin() && prev(it)->first.second > l) {
    auto pr = prev(it);
    if (pr->first.second >= r) {
      auto t = *pr;
      op[col].push_back(std::make_pair(t.second + 1, tot));
      st.insert(std::make_pair(std::make_pair(l, r), col));
      if (t.first.first < l)
        st.insert(std::make_pair(std::make_pair(t.first.first, l), t.second));
      if (t.first.second > r)
        st.insert(std::make_pair(std::make_pair(r, t.first.second), t.second));
      st.erase(t);
      return;
    }
    del.push_back(*pr);
    if (pr->first.first < l)
      ins.push_back(
          std::make_pair(std::make_pair(pr->first.first, l), pr->second));
    op[col].push_back(std::make_pair(pr->second + 1, pr->first.second - l));
    tot -= pr->first.second - l;
  }
  for (; it != st.end() && it->first.first <= r; ++it) {
    del.push_back(*it);
    if (it->first.second <= r) {
      op[col].push_back(
          std::make_pair(it->second + 1, it->first.second - it->first.first));
      tot -= it->first.second - it->first.first;
    } else {
      op[col].push_back(std::make_pair(it->second + 1, r - it->first.first));
      tot -= r - it->first.first;
      ins.push_back(
          std::make_pair(std::make_pair(r, it->first.second), it->second));
    }
  }
  op[col].push_back(std::make_pair(1, tot));
  for (auto t : del) st.erase(t);
  for (auto t : ins) st.insert(t);
  del.clear();
  ins.clear();
  st.insert(std::make_pair(std::make_pair(l, r), col));
}
long long calc(int len) {
  long long ret = 0;
  std::fill(tag, tag + n + 1, 0);
  for (int l = 1, r = 1, cur = 0; r <= n; ++r) {
    for (auto t : op[r]) {
      if (t.first <= l)
        cur += t.second;
      else
        tag[t.first] += t.second;
      tag[r + 1] -= t.second;
    }
    while (l < r && cur + tag[l + 1] >= len) ++l, cur += tag[l];
    if (cur >= len) ret += l;
  }
  return ret;
}
long long sum[300005], sum1[300005];
long long _ask(int p) {
  long long ret = 0;
  while (p) ret += sum[p], p -= p & (-p);
  return ret;
}
long long _ask1(int p) {
  long long ret = 0;
  while (p) ret += sum1[p], p -= p & (-p);
  return ret;
}
inline void _add(int p, long long v) {
  while (p <= n) sum[p] += v, p += p & (-p);
}
inline void _add1(int p, long long v) {
  while (p <= n) sum1[p] += v, p += p & (-p);
}
inline long long askpr(int r) { return (r + 1) * _ask(r) - _ask1(r); }
inline void addsuf(int p, int v) { _add(p, v), _add1(p, 1ll * p * v); }
inline long long ask(int l, int r) { return askpr(r) - askpr(l - 1); }
inline void add(int l, int r, int v) { addsuf(l, v), addsuf(r + 1, -v); }
long long calcans(int len) {
  long long ret = 0;
  std::fill(tag, tag + n + 1, 0);
  for (int l = 1, r = 1, cur = 0; r <= n; ++r) {
    for (auto t : op[r]) {
      if (t.first <= l)
        cur += t.second;
      else
        tag[t.first] += t.second;
      tag[r + 1] -= t.second;
      add(t.first, r, t.second);
    }
    while (l < r && cur + tag[l + 1] >= len) ++l, cur += tag[l];
    if (cur >= len) ret += ask(1, l);
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d", a + i, b + i), mx = std::max(b[i], mx);
  for (int i = 1; i <= n; ++i) insert(a[i], b[i], i);
  int l = 1, r = mx;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (calc(mid) >= k)
      l = mid;
    else
      r = mid - 1;
  }
  long long ans = 0;
  ans = calcans(l + 1) + 1ll * l * (k - calc(l + 1));
  printf("%lld\n", ans);
  return 0;
}
