小D是小C的朋友,非常喜欢间隔而不是数字“$$$3$$$”。
现在他在数轴上有$$$n$$$个间隔,其中第$$$i$$$个是$$$[a_i,b_i]$$$。
只有$$$n$$$区间不能满足他。他将区间 $$$[l,r]$$$ 的区间值($$$1 \leq l \leq r \leq n$$$、$$$l$$$ 和 $$$r$$$ 都是整数)定义为从第 $$$l$$$ 到第 $$$r$$$ 的区间并集的总长度。
他想精确地选择 $$$k$$$ 不同的区间间隔,使得它们的值之和最大。请帮他算一下最大和。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq k \leq \min\{\frac{n(n+1)}{2},10^9\}$$$) — 小 D 拥有的区间数和他将选择的区间数。
接下来的 $$$n$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$,$$$n$$$ 行中的第 $$$i$$$ 行描述第 $$$i$$$ 区间 ($$$1 \leq a_i < b_i \leq 10^9$$$)。
输出
打印一个整数——小 D 可以获得的最大数值之和。
示例
输入 #1
2 1 1 3 2 4
输出 #1
3
输入 #2
3 3 1 4 5 7 3 6
输出 #2
15
注意
第一个例子,小D会选择$$$[1,2]$$$,第一个区间和第二个区间的并集是$$$[1,4]$$$,其长度是$$$3$$$。
第二个例子,小D会选择$$$[1,2]$$$、$$$[2,3]$$$和$$$[1,3]$$$,答案是$$$5+6+4=15$$$。