#include <bits/stdc++.h>
using namespace std;
struct point {
  int x, id;
};
struct node {
  int l, r, t;
  inline void in() { scanf("%d%d", &l, &r), --r; }
  inline bool operator<(const node &a) const { return l < a.l; }
} a[500005];
int n, K;
long long sta[2][500005];
int f[500005], shu[500005], pos[500005];
set<node> cc;
vector<point> buc[500005];
inline void T_add(int x, int y) {
  long long num = 1ll * x * y;
  for (; x <= n; x += x & -x) sta[0][x] += y, sta[1][x] += num;
}
inline long long query(int opt, int x) {
  long long sum = 0;
  for (; x; x -= x & -x) sum += sta[opt][x];
  return sum;
}
inline int calc_(int x) {
  memset(shu, 0, sizeof(shu));
  int ans = 0, cnt = 0, head = 1;
  for (int i = 1; i <= n; ++i) {
    ans += f[i];
    int size = buc[i].size();
    for (int j = 1; j <= size; ++j) {
      point t = buc[i][j - 1];
      if (t.id < head)
        ans += t.x;
      else
        shu[t.id] += t.x;
    }
    while (head <= i && ans >= x) {
      ans += shu[head];
      ans -= a[head].r - a[head].l + 1;
      ++head;
    }
    cnt += head - 1;
    pos[i] = head - 1;
    if (cnt > K) return K + 1;
  }
  return cnt;
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; ++i) a[i].in();
  for (int i = 1; i <= n; ++i) {
    f[i] = a[i].r - a[i].l + 1;
    while (cc.size()) {
      set<node>::iterator it;
      it = cc.upper_bound((node){a[i].l - 1, 0, 0});
      if (it == cc.end()) break;
      if (it->l > a[i].r) break;
      f[i] -= min(it->r, a[i].r) - it->l + 1;
      buc[i].push_back((point){min(it->r, a[i].r) - it->l + 1, it->t});
      int l = a[i].r + 1, r = it->r, t = it->t;
      cc.erase(it);
      if (l <= r) cc.insert((node){l, r, t});
    }
    if (cc.size() && cc.begin()->l < a[i].l) {
      set<node>::iterator it;
      it = cc.upper_bound((node){a[i].l - 1, 0, 0});
      it--;
      if (it->r >= a[i].l) {
        f[i] -= min(it->r, a[i].r) - a[i].l + 1;
        buc[i].push_back((point){min(it->r, a[i].r) - a[i].l + 1, it->t});
        int l = it->l, r = it->r, t = it->t;
        cc.erase(it);
        cc.insert((node){l, a[i].l - 1, t});
        if (r > a[i].r) cc.insert((node){a[i].r + 1, r, t});
      }
    }
    cc.insert((node){a[i].l, a[i].r, i});
  }
  int Min, num;
  for (int l = 1, r = 1e9, mid, cnt; l <= r;) {
    mid = l + r >> 1;
    cnt = calc_(mid);
    if (cnt > K)
      l = mid + 1;
    else
      Min = mid, r = mid - 1;
  }
  num = calc_(Min);
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    int size = buc[i].size();
    for (int j = 1; j <= size; ++j) {
      point t = buc[i][j - 1];
      T_add(t.id, -t.x);
    }
    T_add(i, a[i].r - a[i].l + 1);
    if (pos[i]) {
      ans += query(1, pos[i]);
      ans += (query(0, i) - query(0, pos[i])) * pos[i];
    }
  }
  printf("%lld\n", ans + 1ll * (K - num) * (Min - 1));
}
