Little D is a friend of Little C who loves intervals very much instead of number "3".

Now he has n intervals on the number axis, the i-th of which is [a_i,b_i].

Only the n intervals can not satisfy him. He defines the value of an interval of intervals [l,r] (1 ≤ l ≤ r ≤ n, l and r are both integers) as the total length of the union of intervals from the l-th to the r-th.

He wants to select exactly k different intervals of intervals such that the sum of their values is maximal. Please help him calculate the maximal sum.

Input

First line contains two integers n and k (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ k ≤ min\{(n(n+1))/(2),10^9\}) — the number of intervals Little D has and the number of intervals of intervals he will select.

Each of the next n lines contains two integers a_i and b_i, the i-th line of the n lines describing the i-th interval (1 ≤ a_i < b_i ≤ 10^9).

Output

Print one integer — the maximal sum of values Little D can get.

Examples

Input

2 1
1 3
2 4


Output

3

Input

3 3
1 4
5 7
3 6


Output

15

Note

For the first example, Little D will select [1,2], the union of the first interval and the second interval is [1,4], whose length is 3.

For the second example, Little D will select [1,2], [2,3] and [1,3], the answer is 5+6+4=15.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const long long LL_INF = 1ll * INF * INF;
const int MAX_N = 300000 + 7;
const int mod = INF;
template <typename T>
inline void addmod(T& a, const long long& b, const int& MOD = mod) {
  a = (a + b) % MOD;
  if (a < 0) a += MOD;
}
int n, k;
int cost(pair<int, int>& a) { return a.second - a.first + 1; }
class FenWickTree {
 public:
  void update(int x, int val) {
    for (int t = x; t < MAX_N; t += t & -t) {
      tree[t] += val;
      inc_tree[t] += 1ll * x * val;
    }
  }
  long long get(int x) {
    long long res = 0;
    for (int t = x; t > 0; t -= t & -t) {
      res += tree[t];
    }
    return res;
  }
  long long get_inc(int x) {
    long long res = 0;
    for (int t = x; t > 0; t -= t & -t) {
      res += inc_tree[t];
    }
    return res;
  }
  long long calc(int u, int v) { return get(v + 1) - get(u); }
  long long calc_inc(int u, int v) {
    return get_inc(u) + 1ll * (u + 1) * calc(u, v);
  }

 private:
  static const int MAX_N = ::MAX_N;
  long long tree[MAX_N];
  long long inc_tree[MAX_N];
} fenwickTree;
pair<int, int> nil = {0, -1};
vector<pair<int, int>> s;
set<pair<int, int>> rev[MAX_N];
vector<pair<int, int>> updated[MAX_N];
inline void insert_to_tree(map<pair<int, int>, int>& mapping, pair<int, int> a,
                           int i, int& sum, bool calc_sum, int cur_index) {
  mapping[a] = i;
  rev[i].insert(a);
  sum += cost(a);
  updated[cur_index].push_back({i, cost(a)});
  if (calc_sum) {
    fenwickTree.update(i + 1, cost(a));
  }
}
inline void remove_seg_from_tree(map<pair<int, int>, int>& mapping,
                                 pair<int, int>& a, int i, int& sum,
                                 bool calc_sum, int cur_index) {
  rev[i].erase(a);
  mapping.erase(a);
  sum -= cost(a);
  updated[cur_index].push_back({i, -cost(a)});
  if (calc_sum) {
    fenwickTree.update(i + 1, -cost(a));
  }
}
inline void add(map<pair<int, int>, int>& mapping, int i, int& sum,
                bool calc_sum = false) {
  pair<int, int>& cur = s[i];
  for (bool found = true; found;) {
    found = false;
    auto it = mapping.lower_bound(cur);
    if (it != mapping.end()) {
      pair<pair<int, int>, int> on_tree = *it;
      if (on_tree.first.first <= cur.second) {
        remove_seg_from_tree(mapping, on_tree.first, on_tree.second, sum,
                             calc_sum, i);
        if (on_tree.first.second > cur.second) {
          insert_to_tree(mapping, {cur.second + 1, on_tree.first.second},
                         on_tree.second, sum, calc_sum, i);
        }
        found = true;
      }
    }
  }
  auto it = mapping.lower_bound(cur);
  if (it != mapping.begin()) {
    --it;
    pair<pair<int, int>, int> on_tree = *it;
    if (on_tree.first.second >= cur.first) {
      remove_seg_from_tree(mapping, on_tree.first, on_tree.second, sum,
                           calc_sum, i);
      insert_to_tree(mapping, {on_tree.first.first, cur.first - 1},
                     on_tree.second, sum, calc_sum, i);
      if (on_tree.first.second > cur.second) {
        insert_to_tree(mapping, {cur.second + 1, on_tree.first.second},
                       on_tree.second, sum, calc_sum, i);
      }
    }
  }
  insert_to_tree(mapping, cur, i, sum, calc_sum, i);
}
void init() {
  map<pair<int, int>, int> mapping;
  int cur_sum = 0;
  for (int i = (0), _b = (n); i < _b; ++i) rev[i].clear();
  for (int i = 0; i < n; ++i) {
    ::add(mapping, i, cur_sum, false);
  }
}
bool check(int min_sum) {
  map<pair<int, int>, int> mapping;
  long long total = 0;
  int j = 0;
  int cur_sum = 0;
  static int added[MAX_N];
  fill_n(added, n, 0);
  int found = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < updated[i].size(); ++j)
      if (updated[i][j].first >= found) {
        int t = updated[i][j].first;
        added[t] += updated[i][j].second;
        cur_sum += updated[i][j].second;
      }
    while (found < i && cur_sum - added[found] >= min_sum) {
      cur_sum -= added[found];
      added[found] = 0;
      ++found;
    }
    if (cur_sum >= min_sum) {
      total += found + 1;
    }
  }
  return total >= k;
}
long long calc(int min_sum) {
  map<pair<int, int>, int> mapping;
  int cur_sum = 0;
  long long res = 0;
  long long total = 0;
  for (int i = (0), _b = (n); i < _b; ++i) rev[i].clear();
  int found = 0;
  for (int i = 0; i < n; ++i) {
    ::add(mapping, i, cur_sum, true);
    while (found + 1 <= i && cur_sum - fenwickTree.get(found + 1) >= min_sum)
      ++found;
    if (cur_sum - fenwickTree.get(found) >= min_sum) {
      res += fenwickTree.calc_inc(found, i);
      total += found + 1;
      long long excessed = total - k;
      if (excessed > 0) {
        long long now = min(excessed, res / min_sum);
        res -= now * min_sum;
        total -= now;
      }
    }
  }
  long long excessed = total - k;
  if (excessed > 0) {
    long long now = min(excessed, res / min_sum);
    res -= now * min_sum;
    total -= now;
  }
  return res;
}
void solve() {
  cin >> n >> k;
  s.resize(n);
  int mx = 0;
  for (int i = (0), _b = (n); i < _b; ++i) {
    cin >> s[i].first >> s[i].second;
    s[i].second--;
    mx = max(mx, s[i].second);
  }
  init();
  int low = 1, high = mx, min_sum = 0;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (check(mid)) {
      min_sum = mid;
      low = mid + 1;
    } else
      high = mid - 1;
  }
  cerr << "min_sum"
       << ": " << (min_sum) << '\n';
  ;
  long long res = calc(min_sum);
  cout << res << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}
