描述

因果性是理论物理学中一个非常重要的概念。讨论因果性的基本元素是事件。一个事件$e$由其发生的时间$t$和位置$x$描述，记作$e = (t, x)$。在我们的讨论中，所有事件都发生在一维几何空间中，因此位置由$x$轴上的一个实数坐标$x$表示。通常，理论物理学家喜欢将光速定义为$1$，这样时间和空间具有相同的单位（实际的物理单位会让理论学家感到害怕和困惑）。

一个事件$e_1 = (t_1, x_1)$可能是另一个事件$e_2 = (t_2, x_2)$的可能原因，如果从$e_1$发出的信号可以到达$e_2$。由于信号不能超过光速传播，因此该条件可以表示为：

$e_1$是$e_2$的可能原因，当且仅当$t_2 \geq t_1 + |x_2 - x_1|$

例如，事件$(-1, 1)$可能是$(0, 0)$、$(1, 2)$和$(1, 3)$的原因，但不能是$(1, 4)$或$(-2, 1)$的原因。注意，一个事件可以成为多个其他事件的原因。

最近，科学家在一维几何宇宙中观测到了几个异常事件。根据现有理论，他们知道这些观测结果是由多少个原因引起的，但他们不知道这些原因的时间和空间坐标。你需要编写一个程序，确定**最早原因**可能发生的最晚时间（即至少有一个原因必须在这个时间或更早发生）。值得注意的是，所有观测到的事件的时间和空间坐标都是整数，且满足$-1000000 \leq t, x \leq 1000000$。

右图展示了输入的第一个样例：一个最早的事件作为所有四个事件的可能原因。

输入

第一行是测试用例的数量。每个测试用例的第一行包含两个整数$n$和$m$，分别表示事件的数量和原因的数量，满足$1 \leq n$, $m \leq 100000$。接下来的$n$行，每行包含两个整数$t$和$x$，表示每个事件的时间和空间坐标。

输出

对于每个测试用例，输出一行，格式如样例所示，给出最早原因可能发生的最晚时间。由于时间单位不可分割，该时间一定是一个整数。

样例输入

4
4 1
1 -1
1 3
1 4
2 6
4 2
1 -1
1 3
1 4
2 6
4 3
1 -1
1 3
1 4
2 6
4 4
1 -1
1 3
1 4
2 6

样例输出

Case 1: -2
Case 2: 0
Case 3: 0
Case 4: 1

来源

Waterloo local 2004.01.31