#include <bits/stdc++.h>
using namespace std;
int n;
int K;
struct node {
  int l, r;
  mutable int t;
  node(int l = 0, int r = 0, int t = 0) : l(l), r(r), t(t) {}
  bool operator<(const node &B) const { return l < B.l; }
};
set<node> Tr;
set<node>::iterator split(int pos) {
  set<node>::iterator u = Tr.lower_bound(pos);
  if (u != Tr.end() && (*u).l == pos) return u;
  u--;
  if ((*u).r == pos) return Tr.end();
  node t = *u;
  Tr.erase(u);
  Tr.insert(node(t.l, pos, t.t));
  return Tr.insert(node(pos, t.r, t.t)).first;
}
vector<pair<int, int> > G[300005];
int ad[300005];
pair<long long, long long> chk(int mid) {
  pair<long long, long long> ret;
  long long sm = 0;
  int L = 0, val = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < G[i].size(); j++) {
      if (G[i][j].first > L)
        ad[G[i][j].first] += G[i][j].second;
      else
        val += G[i][j].second, sm += G[i][j].second * (L - G[i][j].first + 1ll);
      ad[i + 1] -= G[i][j].second;
    }
    for (; L + 1 <= i && val + ad[L + 1] >= mid; L++)
      val += ad[L + 1], sm += val;
    ret.first += L, ret.second += sm;
  }
  for (int i = 1; i <= n; i++) ad[i] = 0;
  return ret;
}
int main() {
  scanf("%d%d", &n, &K);
  Tr.insert(node(1, 1e9));
  for (int i = 1, a, b; i <= n; i++) {
    scanf("%d%d", &a, &b);
    set<node>::iterator r = split(b), l = split(a);
    for (; l != r;) {
      node t = *l;
      Tr.erase(l++);
      G[i].push_back(make_pair(t.t + 1, t.r - t.l));
    }
    Tr.insert(node(a, b, i));
  }
  int L = 1, R = 1e9, mid;
  for (; L < R;) {
    mid = L + R + 1 >> 1;
    pair<long long, long long> t = chk(mid);
    if (t.first >= K)
      L = mid;
    else
      R = mid - 1;
  }
  pair<long long, long long> ans = chk(L);
  printf("%lld\n", ans.second - (ans.first - K) * L);
}
