← 返回题目列表

Codeforces · 649/E

E. 巴士

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

沿路有 n 个旅行者。道路是一条直线;旅行者的尺寸可以忽略不计,将其视为点。

公交车司机 Vasily 借助移动应用程序,知道每个旅客所站的 xi 点。此外,他还知道第 i 个旅行者想要乘坐公共汽车旅行的距离 di 。因此,第 i 个旅客计划在 xi + di 点下车。现在瓦西里想要决定让哪些旅行者搭车,以及让哪些旅行者在路边沾满灰尘。

瓦西里决定今天他应该赚很多钱,所以他决定运送一名旅行者。车队包括所有类型的巴士。巴士上的座位越多,租金就越贵。

帮助 Vasily 确定巴士上足以运送一名旅客的最小乘客座位数。巴士上的旅客人数在任何时候都不能多于巴士上的乘客座位。瓦西里本人可以决定他将乘坐巴士运送哪些特定的旅客。

考虑到公共汽车总是从左向右行驶(从较小的坐标到较大的坐标),并从最左边旅行者的左侧开始其旅程。如果某个时刻,一名旅客需要下车,而另一名旅客需要上车,请考虑一名旅客先下车,然后另一名旅客才能上车。

输入

输入的第一行包含两个正整数 n 和 a (1 ≤ a ≤ n ≤ 200 000) — 沿路站立的旅行者数量以及 Vasily 想要搭便车的最少旅行者数量。

接下来的 n 行每行包含两个整数 xi 和 di (1 ≤ xi, di ≤ 109) — 第 i 个旅行者所在的坐标,以及他想要乘坐公共汽车旅行的距离。旅行者坐标以随机顺序给出。某一时刻可能有多名旅客。

输出

首先打印一个整数——公共汽车上的最小乘客座位数,足以运送至少一名旅客。

然后打印一个整数——瓦西里要搭便车的旅客人数。旅行者按照输入数据中指定的顺序从 1 开始编号。数字可以按任何顺序显示。如果有多个答案,您可以显示其中任何一个。

示例

输入 #1

3 2
8 9
3 5
1 3

输出 #1

1
1 3

输入 #2

5 4
20 40
10 10
15 5
5 15
20 30

输出 #2

2
4 2 5 1

注意

在第一个测试用例中,单座巴士就足够了。例如,瓦西里可以载第三位和第一位旅客,或者第二位和第一位旅客。