D. 区间的区间

时间限制：2 秒
内存限制：256 MB

小 D 是小 C 的朋友，他非常喜欢区间，而不是数字 “3”。

现在他在数轴上有 $n$ 个区间，第 $i$ 个区间为 $[a_i, b_i]$。

只有这 $n$ 个区间还不能满足他。他定义区间之区间 $[l, r]$（其中 $1 \le l \le r \le n$，$l$ 和 $r$ 均为整数）的价值为：第 $l$ 个区间到第 $r$ 个区间的并集的总长度。

他想选择恰好 $k$ 个不同的区间之区间，使得它们的价值和最大。请帮他计算出这个最大和。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 3 \cdot 10^5$，$1 \le k \le \min\left\{\frac{n(n+1)}{2},\ 10^9\right\}$）—— 小 D 拥有的区间数量，以及他将选择的区间之区间的数量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，描述第 $i$ 个区间（$1 \le a_i < b_i \le 10^9$）。

输出格式

输出一个整数 —— 小 D 能得到的最大价值和。

示例

输入

2 1
1 3
2 4

输出

3

输入

3 3
1 4
5 7
3 6

输出

15

样例解释

第一个样例：
小 D 会选择 $[1, 2]$，第一个区间和第二个区间的并集是 $[1, 4]$，长度为 $3$。

第二个样例：
小 D 会选择 $[1, 2]$、$[2, 3]$ 和 $[1, 3]$，它们的价值分别是 $5$、$6$ 和 $4$，总和为 $15$。