#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
  x *= f;
}
set<pair<int, int> > st;
set<pair<int, int> >::iterator it, itt;
vector<pair<int, int> > v[300010];
int n, k;
int L[300010];
int main() {
  read(n);
  read(k);
  st.insert(make_pair(1, 0));
  st.insert(make_pair(1e9 + 1, 0));
  for (int i = 1; i <= n; ++i) {
    int l, r;
    read(l);
    read(r);
    r--;
    it = st.upper_bound(make_pair(l, n));
    itt = it;
    --it;
    if (itt->first <= r + 1) {
      v[i].push_back(make_pair(it->second + 1, itt->first - l));
      if (it->first == l) st.erase(it);
      it = itt;
      ++itt;
    }
    while (true) {
      if (itt->first > r + 1) break;
      v[i].push_back(make_pair(it->second + 1, itt->first - it->first));
      st.erase(it);
      it = itt;
      ++itt;
    }
    if (it->first <= l) {
      v[i].push_back(make_pair(it->second + 1, r - l + 1));
      st.insert(make_pair(r + 1, it->second));
      if (it->first == l) st.erase(it);
    } else if (it->first != r + 1) {
      v[i].push_back(make_pair(it->second + 1, r - it->first + 1));
      st.insert(make_pair(r + 1, it->second));
      st.erase(it);
    }
    st.insert(make_pair(l, i));
  }
  int l = 1, r = 1e9;
  long long ans = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    int ll = 1;
    long long cnt = 0, kk = 1ll * n * (n - 1) / 2 + n, s = 0;
    memset(L, 0, sizeof(L));
    for (int i = 1; i <= n; ++i) {
      int si = v[i].size();
      for (int j = 0; j < si; ++j) {
        int pos = v[i][j].first, val = v[i][j].second;
        if (pos < ll)
          L[ll] += val, s += 1ll * (ll - pos) * val, L[i + 1] -= val;
        else
          L[pos] += val, L[i + 1] -= val;
      }
      while (L[ll] >= mid && ll != i + 1) s += L[ll], L[ll + 1] += L[ll], ++ll;
      kk -= i - ll + 1;
      cnt += s;
    }
    if (kk == k) {
      cout << cnt << endl;
      return 0;
    } else if (kk < k)
      ans = cnt + (k - kk) * (mid - 1), r = mid - 1;
    else
      l = mid + 1;
  }
  cout << ans << endl;
  return 0;
}
