U182925 水题

因为消防员叔叔要救火，所以这是道大水题

数轴上有一些地方着火了。 给出n片区域，每片区域着火的范围$l_i$, $r_i$，表示在[$l_i$, $r_i$]上着火了。区域有可能重叠。 现在有m位消防员叔叔，每位消防员叔叔力大无穷，一只手拿着一个水管，所以可以以1个单位每秒的速度向两端灭火。由于消防员叔叔神通广大，他们可以被派遣到数轴上任意一个地方。派遣的第一秒消防员叔叔会先把他被派遣的位置上的火灭了，如果那里没有火会等其他叔叔一起行动（在第二秒再开始向两旁灭火）。 作为总指挥的你要选择将消防员叔叔派遣到数轴上的哪个地方可以尽快灭火，并计算出火能被灭掉的最短时间。有可能不需要派出全部的消防员叔叔，所以记得输出有多少位消防员叔叔可以休息，如果没有输出一个整数"0"。

输入共（n+1）行。 第一行输入两个整数n, m。 接下来n行每行输入一个整数对$l_i$, $r_i$。

输出共2行。 第一行输出两个整数，表示火能被灭掉的最短时间（秒）和可以休息的消防员叔叔的位数。 第二行按数轴上从左到右的顺序输出被派出的消防员叔叔的位置。 答案可能有多个，输出字典序最大的那个。

【样例1解释】 派一位消防员到0。 第一秒全部火灭了。 【样例2解释】 分别派三位消防员到-7,-2,3。 第一秒-7,-2,3火灭了。 第二秒-8,-7,-6,-3,-2,-1,2,3,4火灭了。 第三秒全部火灭了。 【数据范围】 对于10%的测试点，n, m=3, $|l_i|$, $|r_i|$≤10. 对于另外10%的测试点， $l_i$=$r_i$。 对于40%的测试点，n, m≤1000, $|l_i|$, $|r_i|$≤10000。 对于60%的测试点，n, m≤10$^4$, $|l_i|$, $|r_i|$≤10$^9$。 对于所有测试点，保证1≤n,m≤10$^5$，0≤$|l_i|$, $|r_i|$≤10$^{18}$, $l_i$≤$r_i$。