Advanced Causal Measurements (ACM)

Causality is a very important concept in theoretical physics. The basic elements in a discussion of causality are events. An event $e$ is described by its time of occurrence $t$ and its location $x$, and we write $e = (t, x)$. For our concerns, all events happen in a one-dimensional geometric space, so a location is a single real number $x$ (a coordinate on the $x$-axis). Theoretical physicists like to set the speed of light to $1$, so that time and space share the same units.

One event $e_1 = (t_1, x_1)$ is a possible cause of a second event $e_2 = (t_2, x_2)$ if a signal emitted at $e_1$ could reach $e_2$. A signal cannot travel faster than light, so this condition can be written as

$e_1 \text{ is a possible cause of } e_2 \iff t_2 \ge t_1 + |x_2 - x_1|.$

Thus an event at $(-1, 1)$ could cause events at $(0, 0)$, $(1, 2)$, and $(1, 3)$, but could not have caused events at $(1, 4)$ or $(-2, 1)$. Note that a single event can cause several others.

Scientists have observed several unusual events in this one-dimensional universe. From current theory they know how many causes were responsible for these observations, but they know nothing about the times and locations of those causes. There are exactly $m$ causes, and every observed event must have at least one of these $m$ causes as a possible cause.

Write a program that determines the latest time at which the earliest cause could have occurred — that is, the largest integer $T$ such that, no matter how the $m$ causes are placed, at least one cause occurs at time $T$ or earlier. Equivalently, place the $m$ causes so that they are possible causes of all observed events while making the earliest cause time as large as possible, and report that time.

All observed events have integer coordinates with $-1000000 \le t, x \le 1000000$.

The first line contains the number of test cases. Each test case begins with a line containing the number of events $n$ and the number of causes $m$ ($1 \le n, m \le 100000$). The next $n$ lines each contain the coordinates $t$ and $x$ of one event.

For each test case, print a single line Case k: a, where $k$ is the test case number (starting from $1$) and $a$ is the latest time at which the earliest cause could have occurred. This value is always an integer, because our time units are not divisible.