沿路有 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
注意
在第一个测试用例中,单座巴士就足够了。例如,瓦西里可以载第三位和第一位旅客,或者第二位和第一位旅客。