CF1034D Intervals of Intervals

小 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\left\{\frac{n(n+1)}{2}, 10^9\right\}$），分别表示小 D 拥有的区间数量和他要选择的区间组数量。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，第 $i$ 行描述第 $i$ 个区间（$1 \leq a_i < b_i \leq 10^9$）。

输出一个整数，表示小 D 能获得的最大价值和。

对于第一个样例，小 D 会选择 $[1,2]$，第一个区间和第二个区间的并集为 $[1,4]$，长度为 $3$。 对于第二个样例，小 D 会选择 $[1,2]$、$[2,3]$ 和 $[1,3]$，答案为 $5+6+4=15$。 由 ChatGPT 4.1 翻译