#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 50;
inline int gi() {
  char ch = getchar();
  int q = 0, x = 0;
  while (ch < '0' || ch > '9') q = (ch == '-' ? 1 : q), ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return q ? (-x) : x;
}
map<int, int> s;
vector<pair<long long, long long> > del[N];
map<int, int>::iterator it;
map<int, int>::iterator nxt(map<int, int>::iterator it) { return ++it; }
void split(int x) {
  it = s.upper_bound(x), --it;
  if (x != it->first) s[x] = it->second;
  return;
}
int n, k, d[N];
pair<long long, long long> check(int v) {
  for (int i = 0; i <= n + 1; ++i) d[i] = 0;
  long long cnt = 0, sum = 0, now = 0, ns = 0;
  for (int r = 1, l = 1; r <= n; ++r) {
    for (auto j : del[r]) {
      d[j.first] += j.second;
      if (j.first <= l) now += j.second, ns += 1ll * j.second * (l - j.first);
    }
    while (now > v) {
      ns += now;
      now += d[++l];
    }
    cnt += l - 1, sum += ns;
  }
  return pair<long long, long long>(cnt, sum);
}
int main() {
  cin >> n >> k;
  int l, r;
  s[0] = s[1e9] = 0;
  for (int i = 1; i <= n; ++i) {
    l = gi() + 1, r = gi();
    split(l), split(r + 1);
    for (map<int, int>::iterator it = s.lower_bound(l); it->first <= r;) {
      map<int, int>::iterator tp = nxt(it);
      del[i].push_back(
          pair<long long, long long>(it->second + 1, tp->first - it->first));
      s.erase(it);
      it = tp;
    }
    del[i].push_back(pair<long long, long long>(i + 1, -r + l - 1));
    s[l] = i;
  }
  l = 0, r = 1e9;
  int mid, las;
  pair<long long, long long> ans;
  while (l <= r) {
    mid = (l + r) >> 1;
    pair<long long, long long> tmp = check(mid);
    if (tmp.first < k)
      las = mid, ans = tmp, r = mid - 1;
    else
      l = mid + 1;
  }
  cout << ans.second + 1ll * (k - ans.first) * las;
  return 0;
}
