#include <bits/stdc++.h>
using namespace std;
extern inline char gc() {
  static char RR[23456], *seg = RR + 23333, *T = RR + 23333;
  if (seg == T) fread(RR, 1, 23333, stdin), seg = RR;
  return *seg++;
}
inline int read() {
  int p = 0, w = 1;
  char c = gc();
  while (c > '9' || c < '0') {
    if (c == '-') w = -1;
    c = gc();
  }
  while (c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
  return p * w;
}
const int sid = 3e5 + 5;
const int mod = 998244353;
const int inf = 1e9;
struct ivl {
  int l, r, c;
  ivl(int _l, int _r, int _c) : l(_l), r(_r), c(_c) {}
  friend bool operator<(ivl a, ivl b) {
    return a.l < b.l || (a.l == b.l && a.r < b.r);
  }
};
long long k;
int n, L[sid], R[sid], F[sid];
set<ivl> seg;
vector<ivl> cg[sid];
void pret() {
  set<ivl>::iterator I;
  seg.insert(ivl(0, inf + 1, 0));
  for (register int i = 1; i <= n; i++) {
    I = seg.lower_bound(ivl(L[i], inf, 0));
    I--;
    if (I->r >= R[i]) {
      cg[i].push_back(ivl(L[i], R[i], I->c));
      if (I->l < L[i]) seg.insert(ivl(I->l, L[i] - 1, I->c));
      if (I->r > R[i]) seg.insert(ivl(R[i] + 1, I->r, I->c));
      seg.erase(I);
      seg.insert(ivl(L[i], R[i], i));
    } else {
      if (I->r >= L[i]) {
        cg[i].push_back(ivl(L[i], I->r, I->c));
        seg.insert(ivl(I->l, L[i] - 1, I->c));
        seg.erase(I++);
      }
      if (I->r < L[i]) I++;
      while (I->r < R[i]) cg[i].push_back(*I), seg.erase(I++);
      cg[i].push_back(ivl(I->l, R[i], I->c));
      if (I->r > R[i]) seg.insert(ivl(R[i] + 1, I->r, I->c));
      seg.erase(I);
      seg.insert(ivl(L[i], R[i], i));
    }
  }
}
bool check(int v) {
  long long ret = 0;
  int nl = 0;
  for (register int i = 1, j = 1; i <= n; i++) {
    F[i] = R[i] - L[i] + 1;
    nl += F[i];
    for (auto I : cg[i]) {
      F[I.c] -= I.r - I.l + 1;
      if (I.c >= j) nl -= I.r - I.l + 1;
    }
    while (j <= i && nl >= v) nl -= F[j], j++;
    ret += j - 1;
  }
  return ret >= k;
}
void wish() {
  int l = 0, r = 1e9, kth = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      l = mid + 1, kth = mid;
    else
      r = mid - 1;
  }
  int nl = 0;
  long long lst = 0, res = 0, num = 0;
  for (register int i = 1, j = 1; i <= n; i++) {
    F[i] = R[i] - L[i] + 1;
    nl += F[i];
    for (auto I : cg[i]) {
      F[I.c] -= I.r - I.l + 1;
      if (I.c >= j)
        nl -= I.r - I.l + 1;
      else
        num -= 1ll * I.c * (I.r - I.l + 1);
    }
    while (j <= i && nl >= kth) {
      nl -= F[j];
      num += 1ll * j * F[j];
      j++;
    }
    lst += num + 1ll * nl * (j - 1);
    res += j - 1;
  }
  cout << lst - 1ll * kth * (res - k) << endl;
}
int main() {
  cin >> n >> k;
  for (register int i = 1; i <= n; i++) L[i] = read(), R[i] = read() - 1;
  pret();
  wish();
  return 0;
}
