#include <bits/stdc++.h>
using namespace std;
long long n, k, L, R, inf = 1e18, sum[400005], ans;
vector<pair<long long, long long> > vec[400005];
struct l1 {
  long long l, r;
} s[400005];
struct node {
  long long l, r;
  mutable long long v;
  node(long long L, long long R = -1, long long V = 0) : l(L), r(R), v(V) {}
  bool operator<(const node &o) const { return l < o.l; }
};
set<node> st;
set<node>::iterator split(long long pos) {
  set<node>::iterator it = st.lower_bound(node(pos));
  if (it != st.end() && (*it).l == pos) return it;
  it--;
  long long L = (*it).l, R = (*it).r, V = (*it).v;
  st.erase(it);
  st.insert(node(L, pos - 1, V));
  return st.insert(node(pos, R, V)).first;
}
long long solve(long long mid) {
  long long r = 0, now = 0, ans = 0, tot = 0, las = 0;
  memset(sum, 0, sizeof(sum));
  for (long long l = 1; l <= n; l++) {
    now += sum[l];
    while (now < mid && r < n) {
      r++;
      for (long long t = 0; t < vec[r].size(); t++) {
        pair<long long, long long> qwq = vec[r][t];
        long long id = qwq.first, v = qwq.second;
        if (id < l) {
          las += v * id;
        } else {
          las += v * (l - 1);
          now += v;
          sum[id + 1] -= v;
        }
      }
      ans += las;
      tot += l - 1;
    }
    if (now >= mid) las += now, ans += now, tot++;
  }
  if (tot < k) return 0;
  return ans - mid * (tot - k);
}
int main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld%lld", &s[i].l, &s[i].r);
    s[i].r--;
    R += s[i].r - s[i].l + 1;
  }
  L = 1;
  st.insert(node(1, inf, 0));
  for (long long i = 1; i <= n; i++) {
    set<node>::iterator it2 = split(s[i].r + 1), it1 = split(s[i].l), it = it1;
    vec[i].push_back(make_pair(i, s[i].r - s[i].l + 1));
    for (; it != it2; it++) {
      long long L = (*it).l, R = (*it).r, V = (*it).v;
      if (!V) continue;
      vec[i].push_back(make_pair(V, L - R - 1));
    }
    st.erase(it1, it2);
    st.insert(node(s[i].l, s[i].r, i));
  }
  while (L <= R) {
    long long mid = L + R >> 1, now;
    if (now = solve(mid)) {
      L = mid + 1;
      ans = now;
    } else
      R = mid - 1;
  }
  printf("%lld", ans);
}
