#P3358. 最长k可重区间集问题

最长k可重区间集问题

题目描述

给定实直线 L\text{L}nn 个开区间组成的集合 I\mathbf{I},和一个正整数 kk,试设计一个算法,从开区间集合 I\mathbf{I} 中选取出开区间集合 SI\mathbf{S}\subseteq\mathbf{I},使得在实直线 L\text{L} 上的任意一点 xxS\text{S} 中包含 xx 的开区间个数不超过 kk,且 zSz\sum_{z\in\text{S}}\lvert z\rvert 达到最大(z\lvert z\rvert 表示开区间 zz 的长度)。

这样的集合 S\mathbf{S} 称为开区间集合 I\mathbf{I} 的最长 kk 可重区间集。zSz\sum_{z\in\text{S}}\lvert z\rvert 称为最长 kk 可重区间集的长度。

对于给定的开区间集合 I\mathbf{I} 和正整数 kk,计算开区间集合 I\mathbf{I} 的最长 kk 可重区间集的长度。

输入格式

输入的第一行有 22 个正整数 nnkk,分别表示开区间的个数和开区间的可重叠数。接下来的 nn 行,每行有 22 个整数,表示开区间的左右端点坐标 l,rl,r,数据保证 l<rl<r

输出格式

输出最长 kk 可重区间集的长度。

4 2
1 7
6 8
7 10
9 13 
15

提示

对于 100%100\% 的数据,1n5001\le n\le 5001k31\le k\le 3