#P18795. [Omi2022] 蛇梯与传送门

[Omi2022] 蛇梯与传送门

[Omi2022] 蛇梯与传送门

题目描述

有一条从左到右的数轴,一枚棋子从所有传送门端点的左边出发,不断向右移动,直到走到所有端点的右边。

数轴上已经放置了 NN 对双向传送门。第 ii 对的两个端点位于 li,ril_i,r_i,所有端点的位置互不相同。

当棋子从左向右到达某个传送门端点时,它立即传送到配对的另一个端点,然后从那个位置继续向右移动。刚刚通过传送到达的端点不会立即再次触发传送,棋子会继续寻找严格在当前位置右侧的下一个端点。

同一对传送门可以在后续行程中再次触发。每触发一次传送,得分增加 11。

你可以再增加至多 MM 对双向传送门。新端点可以放在任意实数位置,但不能与任何其他端点重合。特别地,可以在任意两个已有端点之间、所有端点左边或所有端点右边放置新端点。

请计算最优放置后能够获得的最大得分。只需要输出最大得分,不需要输出放置方案。

输入格式

第一行包含两个整数 N,MN,M。

接下来 NN 行,每行包含两个整数 li,ril_i,r_i,表示一对已有传送门的两个端点。

输出格式

输出一个整数,表示增加至多 MM 对传送门后能够获得的最大得分。

样例输入

3 1
5 6
1 4
2 3

样例输出

6

样例说明

可以在 0.50.5 和 1.51.5 放置一对新传送门,最终触发传送的次数为 66。

数据范围与分组

  • 1≤N≤1061\le N\le10^6;
  • 0≤M≤1060\le M\le10^6;
  • 1≤li,ri≤2N1\le l_i,r_i\le2N,所有 2N2N 个端点的位置互不相同。
分值 额外限制
10 M=0M=0
M=1M=1
15 对所有传送门均有 ri=li+1r_i=l_i+1
N,M≤500N,M\le500
19 N,M≤105N,M\le10^5
31 无额外限制