题目描述

“连清兵都不会，真菜。”

收到队友这样的评论后，新手小 C 下定决心提升自己。正巧，小 C 的面前来了一队小兵，队伍长度是无限的，而且都是最弱的一种。小 C 给这些小兵按照队列中的排序依次编号 $1,2,3,\ldots$，并打算用原地释放技能的方式杀死小兵。

小 C 手里有 $n$ 个技能，但由于蓝条限制，小 C 只能选择其中的 $m$ 个释放。第 $i$ 个技能释放后，如果编号在 $[l_i,r_i)$ 内的小兵没有死亡，那么它会立即死亡。队列中有小兵死亡后，所有活着的小兵编号不变，不会因为有其他小兵死亡而减小。

可是新手小 C 实在太菜了，他打算向你求助：选择 $m$ 个技能释放后，最多能杀死多少小兵呢？

输入格式

第一行两个整数 $n,m$，表示技能数以及可选的技能数。

接下来 $n$ 行，第 $i$ 行两个整数表示 $l_i,r_i$。

输出格式

一行一个整数表示最多杀死多少小兵。

样例输入

5 2
1 7
4 6
4 9
6 12
10 19

样例输出

15

样例解释

选择第一个技能和最后一个技能，能够分别杀死编号为

$1,2,3,4,5,6$

和

$10,11,12,13,14,15,16,17,18$

的小兵，共 $15$ 个小兵，可以证明是最多的。

数据范围

对于全部的数据，满足：

• $1\le m\le n\le10^6$
• $1\le l_i\le r_i\le10^{18}$