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;
struct node {
  long long area, sum;
  long long lazy = -1, cover;
} seg[2400005];
struct mode {
  long long p, t, i;
  bool operator<(const mode &a) const {
    if (p == a.p) return t > a.t;
    return p < a.p;
  }
};
vector<long long> v;
vector<pair<long long, long long> > fixs[300005];
set<mode> s;
pair<long long, long long> arr[300005];
long long n, hav[300005];
void up(int l, int r, int rt) {
  int m = l + r >> 1;
  seg[rt].area = seg[rt].sum = 0;
  if (seg[rt << 1].cover)
    seg[rt].area += v[m] - v[l];
  else
    seg[rt].sum += seg[rt << 1].sum, seg[rt].area += seg[rt << 1].area;
  if (seg[rt << 1 | 1].cover)
    seg[rt].area += v[r] - v[m];
  else
    seg[rt].sum += seg[rt << 1 | 1].sum, seg[rt].area += seg[rt << 1 | 1].area;
}
void down(int l, int r, int rt) {
  if (!~seg[rt].lazy) return;
  int m = l + r >> 1;
  seg[rt << 1].sum = seg[rt].lazy * (v[m] - v[l] - seg[rt << 1].area);
  seg[rt << 1 | 1].sum = seg[rt].lazy * (v[r] - v[m] - seg[rt << 1 | 1].area);
  seg[rt << 1].lazy = seg[rt].lazy, seg[rt << 1 | 1].lazy = seg[rt].lazy;
  seg[rt].lazy = -1;
}
void build(int l, int r, int rt) {
  seg[rt].area = 0, seg[rt].cover = 0, seg[rt].lazy = -1, seg[rt].sum = 0;
  if (r - l <= 1) return;
  int m = l + r >> 1;
  build(l, m, rt << 1), build(m, r, rt << 1 | 1);
}
void modify(int L, int R, int l, int r, int rt, long long val) {
  if (r - l > 1) down(l, r, rt);
  if (L <= l && R >= r) return seg[rt].cover += val, void();
  int m = l + r >> 1;
  if (L < m) modify(L, R, l, m, rt << 1, val);
  if (R > m) modify(L, R, m, r, rt << 1 | 1, val);
  up(l, r, rt);
}
void modify2(int L, int R, int l, int r, int rt, long long val) {
  if (r - l > 1) down(l, r, rt);
  if (L <= l && R >= r)
    return seg[rt].sum = val * (v[r] - v[l] - seg[rt].area), seg[rt].lazy = val,
           void();
  int m = l + r >> 1;
  if (L < m) modify2(L, R, l, m, rt << 1, val);
  if (R > m) modify2(L, R, m, r, rt << 1 | 1, val);
  up(l, r, rt);
}
void mdfy(int l, int r, long long val) {
  modify(l, r, 0, v.size() - 1, 1, val);
}
void mdfy2(int l, int r, long long val) {
  modify2(l, r, 0, v.size() - 1, 1, val);
}
long long gcover() {
  if (seg[1].cover) return v.back() - v[0];
  return seg[1].area;
}
long long gval() {
  if (seg[1].cover) return 0;
  return seg[1].sum;
}
pair<long long, long long> cal(long long x) {
  build(0, v.size() - 1, 1);
  pair<long long, long long> re = make_pair(0, 0);
  for (int i = n, r = n; i > 0; --i) {
    mdfy(arr[i].first, arr[i].second, 1);
    while (r >= i && gcover() >= x)
      mdfy(arr[r].first, arr[r].second, -1),
          mdfy2(arr[r].first, arr[r].second, n - r + 1), --r;
    re.first += n - r, re.second += gcover() * (n - r) + gval();
  }
  return re;
}
long long check(long long x) {
  long long re = 0, nw = 0;
  for (int i = 1; i <= n; ++i) hav[i] = arr[i].second - arr[i].first;
  for (int i = 1, j = 1; i <= n; re += n - j + 1 + (nw >= x), nw -= hav[i++])
    for (; j <= n && nw < x; nw += hav[j++])
      for (auto t : fixs[j])
        if (t.first >= i) nw -= t.second, hav[t.first] -= t.second;
  return re;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long l = 0, r = 1000000001, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i)
    cin >> arr[i].first >> arr[i].second, v.push_back(arr[i].first),
        v.push_back(arr[i].second);
  for (int i = 1; i <= n; ++i) {
    auto p = s.lower_bound(mode{arr[i].first, 0, i});
    if (p == s.end() || (p->p >= arr[i].second && p->t != 1))
      ;
    else if (p->p > arr[i].second)
      s.insert(mode{arr[i].first, 1, p->i}),
          s.insert(mode{arr[i].second, 0, p->i}),
          fixs[i].push_back(make_pair(p->i, arr[i].second - arr[i].first));
    else {
      if (p->t == 1)
        fixs[i].push_back(make_pair(p->i, p->p - arr[i].first)),
            s.insert(mode{arr[i].first, 1, p->i}), p = s.erase(p);
      pair<long long, long long> ls;
      while (p != s.end() &&
             (p->p < arr[i].second || (p->p == arr[i].second && p->t == 1)))
        if (p->t == 0)
          ls = make_pair(p->p, p->i), p = s.erase(p);
        else
          fixs[i].push_back(make_pair(p->i, p->p - ls.first)), p = s.erase(p);
      if (p != s.end() && p->t == 1)
        fixs[i].push_back(make_pair(ls.second, arr[i].second - ls.first)),
            s.insert(mode{arr[i].second, 0, ls.second});
    }
    s.insert(mode{arr[i].first, 0, i}), s.insert(mode{arr[i].second, 1, i});
  }
  while (l < r) {
    long long mid = l + r >> 1;
    if (check(mid) > k)
      l = mid + 1;
    else
      r = mid;
  }
  sort(v.begin(), v.end()), v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; ++i)
    arr[i].first = lower_bound(v.begin(), v.end(), arr[i].first) - v.begin(),
    arr[i].second = lower_bound(v.begin(), v.end(), arr[i].second) - v.begin();
  auto tmp = cal(l);
  cout << tmp.second + (k - tmp.first) * (l - 1) << "\n";
}
