#include <bits/stdc++.h>
using namespace std;
struct data {
  int l, r, rk;
  bool operator<(const data &a) const { return l != a.l ? l < a.l : r < a.r; }
};
set<data> s;
void work(int p) {
  auto ed = s.upper_bound((data){p + 1, 0, 0});
  data x = *(--ed);
  s.erase(ed);
  if (x.l < p) s.insert((data){x.l, p - 1, x.rk});
  if (p <= x.r) s.insert((data){p, x.r, x.rk});
}
int val[300005], n, k;
vector<pair<int, int> > q[300005];
pair<long long, long long> calc(int v) {
  long long ans = 0, sum = 0, cnt = 0, ans2 = 0;
  memset(val, 0, sizeof(val));
  for (int i = 1, r = 0; i <= n; i++) {
    for (auto j : q[i])
      if (j.second <= r) {
        sum += j.first;
        cnt += 1ll * j.first * (r - j.second + 1);
      } else
        val[j.second] += j.first;
    for (; sum + val[r + 1] >= v;) cnt += (sum += val[++r]);
    ans += r;
    ans2 += cnt;
  }
  return pair<long long, long long>(ans, ans2);
}
int main() {
  scanf("%d%d", &n, &k);
  s.insert((data){1, ((1 << 30) - 233) - 1, 0});
  s.insert((data){((1 << 30) - 233), ((1 << 30) - 233), 0});
  for (int i = 1; i <= n; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    r--;
    work(l);
    work(r + 1);
    auto ed = s.lower_bound((data){l, 0, 0});
    for (; ed->r <= r;) {
      int delta = ed->r - ed->l + 1;
      q[i].push_back(pair<int, int>(delta, ed->rk + 1));
      s.erase(ed);
      ed = s.lower_bound((data){l, 0, 0});
    }
    q[i].push_back(pair<int, int>(-(r - l + 1), i + 1));
    s.insert((data){l, r, i});
  }
  int l = 1, r = ((1 << 30) - 233), val;
  pair<long long, long long> ans;
  while (l <= r) {
    int mid = (l + r) / 2;
    pair<long long, long long> v = calc(mid);
    if (v.first < k)
      r = mid - 1;
    else
      val = mid, ans = v, l = mid + 1;
  }
  printf("%lld", ans.second - 1ll * val * (ans.first - k));
}
