#include <bits/stdc++.h>
int N, l[300001], r[300001];
long long K;
struct segment {
  int l, r, time;
  inline bool operator<(const segment &b) const { return l < b.l; }
};
std::set<segment> S;
std::map<int, int> _op[300001];
std::vector<std::pair<int, int> > op[300001];
struct ans_t {
  long long count, sum;
  inline ans_t operator+(const ans_t &b) const {
    return {count + b.count, sum + b.sum};
  }
};
long long add_tag[300001];
ans_t check(long long mid) {
  for (int i = 1; i <= N; i++) add_tag[i] = 0;
  ans_t res = {0, 0}, cur = {0, 0};
  long long this_ans = 0;
  for (int i = 1; i <= N; i++) {
    for (auto &e : op[i]) {
      cur.sum += std::min<long long>(cur.count, e.first) * e.second;
      add_tag[e.first] += e.second;
      if (e.first > cur.count) this_ans += e.second;
    }
    while (this_ans >= mid) {
      cur.sum += this_ans;
      this_ans -= add_tag[++cur.count];
    }
    res = res + cur;
  }
  return res;
}
int main() {
  scanf("%d%lld", &N, &K);
  for (int i = 1; i <= N; i++) scanf("%d%d", l + i, r + i);
  S.insert({1, 1000000000, 0});
  for (int i = 1; i <= N; i++) {
    std::set<segment>::iterator L = S.lower_bound({l[i] + 1, 0, 0}),
                                R = S.lower_bound({r[i], 0, 0});
    L--;
    std::vector<segment> inside(L, R);
    S.erase(L, R);
    for (auto &e : inside)
      if (e.time) _op[i][e.time] -= e.r - e.l;
    if (inside.front().l < l[i]) {
      S.insert({inside.front().l, l[i], inside.front().time});
      if (inside.front().time)
        _op[i][inside.front().time] += l[i] - inside.front().l;
    }
    if (inside.back().r > r[i]) {
      S.insert({r[i], inside.back().r, inside.back().time});
      if (inside.back().time)
        _op[i][inside.back().time] += inside.back().r - r[i];
    }
    S.insert({l[i], r[i], i});
    _op[i][i] += r[i] - l[i];
  }
  for (int i = 1; i <= N; i++) op[i].assign(_op[i].begin(), _op[i].end());
  int l = 1, r = 1000000000;
  ans_t ans;
  while (l < r) {
    int m = l + r + 1 >> 1;
    ans = check(m);
    if (ans.count >= K)
      l = m;
    else
      r = m - 1;
  }
  ans = check(l);
  printf("%lld\n", ans.sum - (ans.count - K) * l);
  return 0;
}
