← 返回题目列表

Codeforces · 1034/D

D. 间隔的间隔

中文机器翻译题面 查看原题

小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$$$。