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>
#pragma GCC optimize("Ofast,inline")
using namespace std;
namespace Base {
inline char gc(void) {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <class T>
inline void read(T &x) {
  T flag = (T)1;
  x = 0;
  static char ch = getchar();
  for (; ch > '9' || ch < '0'; ch = getchar()) flag = ch == '-' ? -1 : 1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 1) + (x << 3) + (ch & 15);
  x *= flag;
  return;
}
inline void readstr(string &x) {
  x = "";
  static char ch;
  while (isspace(ch = getchar()))
    ;
  while (x += ch, !isspace(ch = getchar()))
    ;
}
inline void readstr(char *s) {
  do *s = getchar();
  while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
  do *(++s) = getchar();
  while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
  *s = 0;
  return;
}
inline void printstr(string x, int num = 0, char ch = '\n') {
  for (int i = num; i < x.size(); ++i) putchar(x[i]);
  putchar(ch);
}
inline void readch(char &x) {
  while (isspace(x = getchar()))
    ;
}
char pf[100000], *o1 = pf, *o2 = pf + 100000;
template <class T>
inline void println(T x, char c = '\n') {
  if (x < 0)
    (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf)++ = 45 : *o1++ = 45),
        x = -x;
  static char s[15], *b;
  b = s;
  if (!x) *b++ = 48;
  for (; x; *b++ = x % 10 + 48, x /= 10)
    ;
  for (; b-- != s; (o1 == o2          ? fwrite(pf, 1, 100000, stdout),
                    *(o1 = pf)++ = *b : *o1++ = *b))
    ;
  (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf)++ = c : *o1++ = c);
}
template <class T>
inline void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
  return;
}
template <class T>
inline void writeln(T x) {
  write(x);
  puts("");
}
template <class T>
inline void writeln(T x, char c) {
  write(x);
  putchar(c);
}
template <class T>
inline void writeln(char c, T x) {
  putchar(c);
  write(x);
}
template <class T>
inline void chkmax(T &x, const T y) {
  x > y ? x = x : x = y;
}
template <class T>
inline void chkmin(T &x, const T y) {
  x < y ? x = x : x = y;
}
template <class T>
inline T max(const T &x, const T &y, const T &z) {
  return x > y ? (x > z ? x : z) : (y > z ? y : z);
}
inline void file(string str) {
  freopen((str + ".in").c_str(), "r", stdin);
  freopen((str + ".out").c_str(), "w", stdout);
}
}  // namespace Base
using namespace Base;
enum { Maxn = 300005, Inf = 1000000000 };
int n, k;
int a[Maxn], b[Maxn], len[Maxn];
struct Segment {
  int l, r, c;
  Segment(int _l = 0, int _r = 0, int _c = 0) : l(_l), r(_r), c(_c) {}
  inline int length(void) { return r - l + 1; }
  inline bool operator<(const Segment &rhs) const {
    return l < rhs.l || (l == rhs.l && r < rhs.r);
  }
};
set<Segment> s;
set<Segment>::iterator its;
vector<Segment> e[Maxn];
vector<Segment>::iterator itv;
inline void Setup(void) {
  s.insert(Segment(0, Inf, 0));
  for (int i = 1; i <= n; i++) {
    its = s.lower_bound(Segment(a[i], Inf, 0));
    --its;
    if (its->r >= b[i]) {
      e[i].push_back(Segment(a[i], b[i], its->c));
      if (its->l < a[i]) s.insert(Segment(its->l, a[i] - 1, its->c));
      if (its->r > b[i]) s.insert(Segment(b[i] + 1, its->r, its->c));
      s.erase(its);
      s.insert(Segment(a[i], b[i], i));
      continue;
    }
    e[i].push_back(Segment(a[i], its->r, its->c));
    if (its->l < a[i]) s.insert(Segment(its->l, a[i] - 1, its->c));
    s.erase(its++);
    if (its->r < a[i]) ++its;
    while (its->r < b[i]) e[i].push_back(*its), s.erase(its++);
    e[i].push_back(Segment(its->l, b[i], its->c));
    if (its->r > b[i]) s.insert(Segment(b[i] + 1, its->r, its->c));
    s.erase(its);
    s.insert(Segment(a[i], b[i], i));
  }
}
inline bool Check(int x) {
  int sum = 0;
  long long cnt = 0;
  for (int i = 1, l = 1; i <= n; i++) {
    sum += (len[i] = b[i] - a[i] + 1);
    for (itv = e[i].begin(); itv != e[i].end(); itv++) {
      len[itv->c] -= itv->length();
      if (itv->c >= l) sum -= itv->length();
    }
    while (sum >= x) sum -= len[l++];
    cnt = cnt + l - 1;
  }
  return cnt >= k;
}
inline long long Solve(int x) {
  int sum = 0;
  long long ans = 0, cnt = 0, now = 0;
  for (int i = 1, l = 1; i <= n; i++) {
    sum += (len[i] = b[i] - a[i] + 1);
    for (itv = e[i].begin(); itv != e[i].end(); itv++) {
      len[itv->c] -= itv->length();
      if (itv->c >= l) sum -= itv->length();
      if (itv->c && itv->c < l) now -= (long long)itv->c * itv->length();
    }
    while (sum >= x) now += (long long)l * len[l], sum -= len[l++];
    ans += now + (long long)sum * (l - 1);
    cnt = cnt + l - 1;
  }
  return ans - (long long)x * (cnt - k);
}
signed main(void) {
  read(n), read(k);
  for (int i = 1; i <= n; i++) read(a[i]), read(b[i]), --b[i];
  Setup();
  int l = 1, r = Inf, ret = 0;
  while (l <= r) {
    int mid = l + r >> 1;
    if (Check(mid))
      ret = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  writeln(Solve(ret));
  return 0;
}
