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 mxN = 3e5;
int n, k, ai, bi, c[mxN], lb = 1, rb = 1e9;
long long a1, a2, s2;
map<int, int> mp{{1, -1}, {1e9, -1}};
vector<array<int, 2>> tp[mxN];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> ai >> bi;
    mp.insert({bi, (--mp.upper_bound(bi))->second});
    mp.insert({ai, (--mp.upper_bound(ai))->second});
    auto it = mp.find(ai);
    while (it->first < bi) {
      tp[i].push_back({it->second, it->first});
      it = mp.erase(it);
      tp[i].back()[1] -= it->first;
    }
    mp[ai] = i;
    tp[i].push_back({i, bi - ai});
  }
  while (lb <= rb) {
    int mb = (lb + rb) / 2;
    a1 = a2 = s2 = 0;
    for (int i1 = 0, i2 = -1, s1 = 0; i1 < n; a1 += i2 + 1, a2 += s2, ++i1) {
      for (array<int, 2> a : tp[i1]) {
        if (a[0] == -1) continue;
        c[a[0]] += a[1];
        if (i2 <= a[0]) s1 += a[1];
        s2 += (long long)min(a[0] + 1, i2 + 1) * a[1];
      }
      while (i2 + 1 <= i1 && s1 - (i1 == -1 ? 0 : c[i2]) >= mb) {
        s1 -= (i1 == -1 ? 0 : c[i2++]);
        s2 += s1;
      }
    }
    if (a1 >= k)
      lb = mb + 1;
    else
      rb = mb - 1;
    memset(c, 0, 4 * n);
  }
  cout << a2 + (k - a1) * rb;
}
