#include <bits/stdc++.h>
using int64 = long long;
constexpr int Maxn(300000);
namespace IOManager {
constexpr int FILESZ(131072);
char buf[FILESZ];
const char *ibuf = buf, *tbuf = buf;
struct IOManager {
  inline char gc() {
    return (ibuf == tbuf) &&
                   (tbuf = (ibuf = buf) + fread(buf, 1, FILESZ, stdin),
                    ibuf == tbuf)
               ? EOF
               : *ibuf++;
  }
  template <class _Tp>
  inline operator _Tp() {
    _Tp s = 0u;
    char c = gc();
    for (; c < 48; c = gc())
      ;
    for (; c > 47; c = gc()) s = (_Tp)(s * 10u + c - 48u);
    return s;
  }
};
}  // namespace IOManager
IOManager::IOManager io;
std::set<std::pair<int, int>> s;
std::vector<std::pair<int, int>> upd[Maxn + 1];
int t[Maxn + 1];
int main() {
  const int n = io, k = io;
  s.insert(std::make_pair(1, 0));
  s.insert(std::make_pair(1e9, 0));
  for (int i = 1; i <= n; ++i) {
    const int l = io, r = io;
    int lasidx;
    auto pre = s.upper_bound(std::make_pair(l, n));
    auto nxt = pre--;
    upd[i].push_back(std::make_pair(lasidx = pre->second, l - nxt->first));
    if (pre->first == l) s.erase(pre);
    upd[i].push_back(std::make_pair(i, r - l));
    s.insert(std::make_pair(l, i));
    for (; nxt->first < r; s.erase(pre))
      pre = nxt++, upd[i].push_back(std::make_pair(lasidx = pre->second,
                                                   pre->first - nxt->first));
    if (r < nxt->first)
      upd[i].push_back(std::make_pair(lasidx, nxt->first - r)),
          s.insert(std::make_pair(r, lasidx));
  }
  int l = 1, r = 1e9;
  int64 t1, s1, s2, as1 = 0, as2 = 0, al = 0;
  int t2;
  for (int m; l < r;
       (k <= s2) ? (l = m + 1, al = m, as1 = s1, as2 = s2) : (r = m)) {
    t1 = t2 = s1 = s2 = 0;
    memset(t + 1, 0, n << 2);
    m = (l + r) >> 1;
    for (int i = 1, j = 1; i <= n; ++i) {
      const int sz = upd[i].size();
      for (int o = 0; o < sz; ++o)
        if (upd[i][o].first < j)
          t1 += (int64)upd[i][o].first * upd[i][o].second;
        else
          t1 += (int64)(j - 1) * upd[i][o].second, t2 += upd[i][o].second,
              t[upd[i][o].first] += upd[i][o].second;
      for (; j <= i && m <= t2; t1 += t2, t2 -= t[j++])
        ;
      s1 += t1;
      s2 += j - 1;
    }
  }
  return printf("%lld", as1 - (as2 - k) * al), 0;
}
