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::max;
using std::min;
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x3f3f3f3f3f3f3f3f;
__inline__ __attribute__((always_inline)) unsigned int rnd() {
  static unsigned int seed = 416;
  return seed += 0x71dad4bfu, seed ^= seed >> 5, seed += 0xc6f74d88u,
         seed ^= seed << 17, seed += 0x25e6561u, seed ^= seed >> 13;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  f && (x = -x);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b,
                                                  const Args &...args) {
  return a < b ? min(a, args...) : min(b, args...);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b,
                                                  const Args &...args) {
  return a < b ? max(b, args...) : max(a, args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 300005;
const int LIMIT = 1e9 + 1;
struct BIT1 {
  long long c[N];
  void add(int x, long long C) {
    ++x;
    for (; x; x -= ((x) & (-(x)))) c[x] += C;
  }
  long long sum(int x) {
    ++x;
    long long ans = 0;
    for (; x < N; x += ((x) & (-(x)))) ans += c[x];
    return ans;
  }
} tr1;
struct BIT2 {
  long long c[N];
  void add(int x, long long C) {
    ++x;
    for (; x < N; x += ((x) & (-(x)))) c[x] += C;
  }
  long long sum(int x) {
    ++x;
    long long ans = 0;
    for (; x; x -= ((x) & (-(x)))) ans += c[x];
    return ans;
  }
} tr2;
struct node {
  int l, r, id;
  __inline__ __attribute__((always_inline)) bool operator<(
      const node &o) const {
    return l < o.l;
  }
};
std::set<node> S;
int n, k;
int L[N], R[N];
std::set<node>::iterator split(int x) {
  auto it = --S.upper_bound((node){x, 0, 0});
  if (it->l == x) return it;
  node val = *it;
  S.erase(it);
  S.insert((node){val.l, x, val.id});
  return S.insert((node){x, val.r, val.id}).first;
}
struct Node {
  int pos, val;
};
std::vector<Node> v[N];
void init() {
  S.insert((node){1, LIMIT, 0});
  for (int i = 1; i <= n; ++i) {
    int l = L[i], r = R[i];
    auto itr = split(r);
    auto itl = split(l);
    for (auto it = itl; it != itr; ++it)
      v[i].push_back((Node){it->id, it->l - it->r});
    S.erase(itl, itr);
    S.insert((node){l, r, i});
  }
}
long long calc(int mid) {
  memset(tr1.c, 0, sizeof(tr1.c));
  int pos = 0;
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (auto it : v[i]) tr1.add(it.pos, it.val);
    tr1.add(i, R[i] - L[i]);
    while (pos < i && tr1.sum(pos + 1) >= mid) ++pos;
    ans += pos;
  }
  return ans;
}
long long solve(int mid) {
  memset(tr1.c, 0, sizeof(tr1.c));
  memset(tr2.c, 0, sizeof(tr2.c));
  int pos = 0;
  long long ans = 0, res = 0;
  for (int i = 1; i <= n; ++i) {
    int l = L[i], r = R[i];
    for (auto it : v[i])
      tr1.add(it.pos, it.val), tr2.add(it.pos, 1ll * it.pos * it.val);
    tr1.add(i, r - l), tr2.add(i, 1ll * i * (r - l));
    while (pos < i && tr1.sum(pos + 1) >= mid) ++pos;
    ans += pos;
    res += tr2.sum(pos) + 1ll * pos * tr1.sum(pos + 1);
  }
  res -= 1ll * (ans - k) * mid;
  return res;
}
int main() {
  read(n, k);
  for (int i = 1; i <= n; ++i) read(L[i], R[i]);
  init();
  int l = 1, r = 1e9;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (calc(mid) >= k)
      l = mid;
    else
      r = mid - 1;
  }
  printf("%lld\n", solve(l));
  return 0;
}
