CF1034D.Intervals of Intervals

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 \leq l \leq r \leq 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.

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

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

仅有这 $n$ 个区间还不能让他满足。他将一个“区间段” $[l,r]$（其中 $1 \leq l \leq r \leq n$，且 $l$、$r$ 均为整数）的值定义为：第 $l$ 个到第 $r$ 个区间（含端点）的并集的总长度。

他希望恰好选出 $k$ 个互不相同的区间段，使得它们的值之和最大。请帮助他计算这个最大和。

First line contains two integers $n$ and $k$ ($1 \leq n \leq 3 \cdot 10^5$, $1 \leq k \leq \min{\frac{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 \leq a_i \lt b_i \leq 10^9$).

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 3 \cdot 10^5$，$1 \leq k \leq \min{\frac{n(n+1)}{2},10^9}$），分别表示 Little D 拥有的区间数量，以及他将选择的“区间之区间”的数量。

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

Print one integer — the maximal sum of values Little D can get.

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

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$.

对于第一个例子，小 D 将选择区间 $[1,2]$，第一个区间与第二个区间的并集为 $[1,4]$，其长度为 $3$。

对于第二个例子，小 D 将选择区间 $[1,2]$、$[2,3]$ 和 $[1,3]$，答案为 $5+6+4=15$。