← 返回题目列表

Codeforces · 754/D

D. Fedor 和优惠券

中文机器翻译题面 查看原题

我们所有的角色都有爱好。费多尔也是如此。他喜欢在附近的超市购物。

超市里的商品都有唯一的整数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 可以选择任意两张优惠券。