【文件读写】本题使用文件读写：输入文件 belt.in，输出文件 belt.out。

题目描述

程老师经营着一家大型分拣中心。中心里有 $m$ 条平行的流水线，编号从 $1$ 到 $m$。每天有大量包裹涌入，程老师需要把每个包裹分配到某条流水线上进行处理。

分拣中心的工作流程是这样的：共有 $n$ 个包裹按到达顺序依次到来，第 $i$ 个包裹在时刻 $t_i$ 到达分拣中心，处理它需要耗费 $p_i$ 个单位时间。输入数据保证 $t_i$ 是非递减的，也就是 $t_1 \le t_2 \le \cdots \le t_n$。当一个包裹到达时，必须立即决定分配到哪条流水线——不存在"暂不分配、等一等再看"的选项。

每条流水线同时只能处理一个包裹，且遵循先来先处理的原则。如果某条流水线上已经有一个或多个包裹在排队，新分配到这条线的包裹必须排在队尾等待，直到它前面所有包裹都处理完毕才能开始。一条流水线处理完某个包裹的瞬间，如果队列中还有下一个包裹，就立刻开始处理下一个，没有空闲间隙。

当一个包裹到来时，程老师会把它分配到空闲时刻最早的那条流水线上。如果有多条流水线的空闲时刻并列最早，则选择编号最小的那条。分配完成后，该包裹就被放入对应流水线的队列中。

这里的"该线空闲时刻"是指该流水线上最后一个排队包裹的完成时刻。如果该流水线当前没有任何包裹在排队，则空闲时刻为 $0$。

包裹被分配到某条线之后，它实际开始处理的时刻，是这条线的空闲时刻与包裹到达时刻 $t_i$ 的较大值——包裹没到不能开工，线没腾出来也不能开工。完成时刻则为开始时刻加上包裹自身的处理耗时 $p_i$。用公式表示就是：

包裹处理完毕后，这条线的空闲时刻更新为该包裹的完成时刻。

所有 $n$ 个包裹都处理完毕后，程老师需要了解两件事：一是最后一个包裹完成处理的时刻（即所有流水线中最后完成的那个时刻），二是在所有流水线中，处理包裹件数最多的那条流水线的编号。如果多条流水线处理件数并列最多，取编号最小的那条。

请你帮程老师算出这两个数。

输入格式

从文件 belt.in 中读入数据。

第一行两个正整数 $n$ 和 $m$，分别表示包裹数量和流水线数量。

接下来 $n$ 行，第 $i$ 行两个正整数 $t_i$ 和 $p_i$，分别表示第 $i$ 个包裹的到达时刻和处理耗时。

输出格式

输出到文件 belt.out 中。

一行两个整数，用空格分隔：第一个整数表示全部包裹处理完毕的时刻，第二个整数表示处理包裹件数最多的流水线编号。

数据范围

对于所有测试点，保证：

• $1 \le n, m \le 10^5$。
• $1 \le t_i, p_i \le 10^9$。
• $t_1 \le t_2 \le \cdots \le t_n$。

各测试点的详细限制如下：

特殊性质 A：$m = 1$。

特殊性质 B：所有 $p_i$ 相同。

样例

样例 1 输入

3 2
1 3
2 2
3 5

样例 1 输出

9 1

样例 2 输入

2 1
1 2
2 2

样例 2 输出

5 1

样例 3 输入

2 3
5 1
5 1

样例 3 输出

6 1

样例解释

对于样例 1，三个包裹的分配过程如下：

• 包裹 1（到达时刻 1，耗时 3）：两条流水线的空闲时刻都是 0，并列最早，选编号最小的线 1。完成时刻 $\max(0, 1)+3=4$，线 1 空闲时刻更新为 4。
• 包裹 2（到达时刻 2，耗时 2）：线 1 空闲时刻为 4，线 2 空闲时刻为 0，线 2 更早，分配到线 2。完成时刻 $\max(0, 2)+2=4$，线 2 空闲时刻更新为 4。
• 包裹 3（到达时刻 3，耗时 5）：线 1 空闲时刻为 4，线 2 空闲时刻也是 4，并列最早，选编号最小的线 1。完成时刻 $\max(4, 3)+5=9$。

最终，全部包裹在时刻 9 处理完毕，线 1 处理了 2 个包裹，线 2 处理了 1 个包裹，件数最多的流水线是线 1。