고급 인과 측정 (Advanced Causal Measurements, ACM)

인과성(causality)은 이론물리학에서 매우 중요한 개념이다. 인과성을 논할 때 기본 단위는 사건(event) 이다. 사건 $e$ 는 발생 시각 $t$ 와 위치 $x$ 로 기술되며 $e = (t, x)$ 로 쓴다. 이 문제에서 모든 사건은 1차원 공간에서 일어나므로, 위치는 $x$축 위의 좌표인 하나의 실수 $x$ 로 주어진다. 이론물리학자들은 흔히 빛의 속력을 $1$ 로 두어 시간과 공간이 같은 단위를 갖도록 한다.

사건 $e_1 = (t_1, x_1)$ 에서 방출된 신호가 사건 $e_2 = (t_2, x_2)$ 에 도달할 수 있으면, $e_1$ 을 $e_2$ 의 가능한 원인(possible cause) 이라고 한다. 어떤 신호도 빛보다 빠를 수 없으므로 이 조건은 다음과 같이 쓸 수 있다.

$e_1 \text{ 이 } e_2 \text{ 의 가능한 원인} \iff t_2 \ge t_1 + |x_2 - x_1|.$

예를 들어 $(-1, 1)$ 에 있는 사건은 $(0, 0)$, $(1, 2)$, $(1, 3)$ 의 사건을 일으킬 수 있지만 $(1, 4)$ 나 $(-2, 1)$ 의 사건은 일으킬 수 없다. 하나의 사건이 여러 사건의 원인이 될 수도 있다.

과학자들이 이 1차원 우주에서 특이한 사건들을 관측했다. 현재 이론으로부터 이 관측을 만들어 낸 원인의 개수는 알지만, 그 원인들의 시각과 위치는 전혀 알지 못한다. 원인은 정확히 $m$ 개이며, 관측된 모든 사건은 이 $m$ 개의 원인 중 적어도 하나를 가능한 원인으로 가져야 한다.

가장 이른 원인이 발생할 수 있었던 가장 늦은 시각을 구하는 프로그램을 작성하라. 즉, $m$ 개의 원인을 어떻게 배치하더라도 적어도 하나의 원인은 시각 $T$ 이하에 발생하게 되는, 가능한 가장 큰 정수 $T$ 를 구하면 된다. 바꿔 말하면, $m$ 개의 원인이 관측된 모든 사건의 가능한 원인이 되도록 배치하면서 가장 이른 원인의 시각을 최대로 만들고, 그 시각을 출력한다.

관측된 모든 사건의 좌표는 정수이며 $-1000000 \le t, x \le 1000000$ 을 만족한다.

첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫 줄에는 사건의 수 $n$ 과 원인의 수 $m$ 이 주어진다 ($1 \le n, m \le 100000$). 이어지는 $n$ 개의 줄에는 각 사건의 좌표 $t$ 와 $x$ 가 주어진다.

각 테스트 케이스마다 한 줄에 Case k: a 형식으로 출력한다. 여기서 $k$ 는 테스트 케이스 번호($1$ 부터 시작)이고, $a$ 는 가장 이른 원인이 발생할 수 있었던 가장 늦은 시각이다. 시간 단위는 나눌 수 없으므로 이 값은 항상 정수이다.