我们所有的角色都有爱好。费多尔也是如此。他喜欢在附近的超市购物。
超市里的商品都有唯一的整数id。此外,对于每个整数,都有一个 id 等于该整数的产品。 Fedor 有 n 张折扣券,其中第 i 张可用于 id 范围从 li 到 ri(含)的产品。今天,Fedor 想要随身携带恰好 k 张优惠券。
Fedor 希望以这样的方式选择 k 个优惠券,即所有优惠券可以与该产品 x 一起使用的此类产品 x 的数量尽可能大(为了更好地理解,请参阅示例)。 Fedor 也想节省他的时间,所以他要求你为他选择优惠券。帮助费多尔!
输入
第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 3·105)——Fedor 拥有的优惠券数量,以及他想要选择的优惠券数量。
接下来的 n 行每行包含两个整数 li 和 ri (- 109 ≤ li ≤ ri ≤ 109) – 第 i 张优惠券的描述。优惠券可以是等额的。
输出
在第一行打印单个整数 - 所有所选优惠券可以使用的最大产品数量。不能使用至少一张优惠券的产品不应计算在内。
在第二行中打印 k 个不同的整数 p1, p2, ..., pk (1 ≤ pi ≤ n) - Fedor 应选择的优惠券的 ID。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 2 1 100 40 70 120 130 125 180
输出 #1
31 1 2
输入 #2
3 2 1 12 15 20 25 30
输出 #2
0 1 2
输入 #3
5 2 1 10 5 15 14 50 30 70 99 100
输出 #3
21 3 4
注意
在第一个示例中,如果我们使用前两张优惠券,则可以使用两张优惠券购买 id 在 [40, 70] 范围内的所有产品。共有31个产品。
在第二个示例中,不能使用两张优惠券购买任何产品,这就是为什么答案为 0。在此示例中,Fedor 可以选择任意两张优惠券。