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>
inline void ckmax(T& x, T y) {
  x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
  x = (y < x ? y : x);
}
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
  if (S == T) {
    T = (S = buf) + fread(buf, 1, SIZE, stdin);
    if (S == T) return '\n';
  }
  return *S++;
}
}  // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
  fwrite(buf, 1, S - buf, stdout);
  S = buf;
}
inline void putchar(char c) {
  *S++ = c;
  if (S == T) flush();
}
struct NTR {
  ~NTR() { flush(); }
} ztr;
}  // namespace Fwrite
namespace Fastio {
struct Reader {
  template <typename T>
  Reader& operator>>(T& x) {
    char c = Fread ::getchar();
    T f = 1;
    while (c < '0' || c > '9') {
      if (c == '-') f = -1;
      c = Fread ::getchar();
    }
    x = 0;
    while (c >= '0' && c <= '9') {
      x = x * 10 + (c - '0');
      c = Fread ::getchar();
    }
    x *= f;
    return *this;
  }
  Reader& operator>>(char& c) {
    c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    return *this;
  }
  Reader& operator>>(char* str) {
    int len = 0;
    char c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    while (c != '\n' && c != ' ') {
      str[len++] = c;
      c = Fread ::getchar();
    }
    str[len] = '\0';
    return *this;
  }
  Reader() {}
} cin;
const char endl = '\n';
struct Writer {
  template <typename T>
  Writer& operator<<(T x) {
    if (x == 0) {
      Fwrite ::putchar('0');
      return *this;
    }
    if (x < 0) {
      Fwrite ::putchar('-');
      x = -x;
    }
    static int sta[45];
    int top = 0;
    while (x) {
      sta[++top] = x % 10;
      x /= 10;
    }
    while (top) {
      Fwrite ::putchar(sta[top] + '0');
      --top;
    }
    return *this;
  }
  Writer& operator<<(char c) {
    Fwrite ::putchar(c);
    return *this;
  }
  Writer& operator<<(char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer& operator<<(const char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer() {}
} cout;
}  // namespace Fastio
const int MAXN = 3e5;
const int MAXR = 1e9;
int n, K;
pair<int, int> seg[MAXN + 5];
vector<pair<int, int> > ev[MAXN + 5];
set<pair<pair<int, int>, int> > s;
void insert(int sl, int sr, int sid) {
  set<pair<pair<int, int>, int> >::iterator it =
      s.lower_bound(make_pair(make_pair(sl, 0), 0));
  if (it != s.begin()) {
    --it;
    if (it->first.second > sl) {
      pair<pair<int, int>, int> tmp = *it;
      s.erase(it);
      s.insert(make_pair(make_pair(tmp.first.first, sl), tmp.second));
      s.insert(make_pair(make_pair(sl, tmp.first.second), tmp.second));
    }
  }
  it = s.lower_bound(make_pair(make_pair(sr, 0), 0));
  if (it != s.begin()) {
    --it;
    if (it->first.second > sr) {
      pair<pair<int, int>, int> tmp = *it;
      s.erase(it);
      s.insert(make_pair(make_pair(tmp.first.first, sr), tmp.second));
      s.insert(make_pair(make_pair(sr, tmp.first.second), tmp.second));
    }
  }
  set<pair<pair<int, int>, int> >::iterator bg =
      s.lower_bound(make_pair(make_pair(sl, 0), 0));
  set<pair<pair<int, int>, int> >::iterator ed = bg;
  if (bg != s.end() && bg->first.second <= sr) {
    int lst = sl;
    do {
      int cl = ed->first.first;
      int cr = ed->first.second;
      if (cl != lst) ev[sid].push_back(make_pair(1, cl - lst));
      ev[sid].push_back(make_pair(ed->second + 1, cr - cl));
      lst = cr;
      ++ed;
    } while (ed != s.end() && ed->first.second <= sr);
    if (lst != sr) ev[sid].push_back(make_pair(1, sr - lst));
    s.erase(bg, ed);
  } else {
    ev[sid].push_back(make_pair(1, sr - sl));
  }
  s.insert(make_pair(make_pair(sl, sr), sid));
}
int f[MAXN + 5];
long long calc(int min_size) {
  for (int i = 1; i <= n; ++i) {
    f[i] = 0;
  }
  int l = 0;
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < ((int)(ev[i]).size()); ++j) {
      int p = ev[i][j].first;
      int v = ev[i][j].second;
      ckmax(p, l);
      f[p] += v;
      f[i + 1] -= v;
    }
    while (l + 1 <= i && f[l + 1] + f[l] >= min_size) {
      f[l + 1] += f[l];
      if (l + 1 > 1) assert(f[l + 1] <= f[l]);
      ++l;
    }
    res += l;
  }
  return res;
}
long long calc_ans(int min_size) {
  for (int i = 1; i <= n; ++i) {
    f[i] = 0;
  }
  int l = 0;
  long long sum = 0, res = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < ((int)(ev[i]).size()); ++j) {
      int p = ev[i][j].first;
      int v = ev[i][j].second;
      if (p <= l) {
        sum += (long long)v * (l - p + 1);
      }
      ckmax(p, l);
      f[p] += v;
      f[i + 1] -= v;
    }
    while (l + 1 <= i && f[l + 1] + f[l] >= min_size) {
      f[l + 1] += f[l];
      sum += f[l + 1];
      ++l;
    }
    res += sum;
  }
  return res;
}
int main() {
  Fastio ::cin >> n >> K;
  for (int i = 1; i <= n; ++i) {
    Fastio ::cin >> seg[i].first >> seg[i].second;
  }
  for (int i = 1; i <= n; ++i) {
    insert(seg[i].first, seg[i].second, i);
  }
  int l = 0, r = MAXR;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (calc(mid) >= K) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  Fastio ::cout << calc_ans(l + 1) + (long long)l * (K - calc(l + 1))
                << Fastio ::endl;
  return 0;
}
