Mummy Madness

Time limit6sMemory limit128 MB

Summary

Given mummy start positions on an infinite grid, compute how many time steps a fleeing player survives when both sides move on a king-step grid.

Level: Hard9 of 10
Topics: Binary search, Geometry, Math, Game theory
Solved: No attempts yet

Problem

On an expedition across the desert you open an ancient Egyptian tomb, and the instant the door swings open the empty sand around you erupts with grumpy mummies. Your only hope is to run and stay ahead of them for as long as possible. Assuming neither you nor the mummies ever tire, how many time steps pass before a mummy finally catches you?

Model the desert as an infinite grid of squares. You and the mummies take turns, and you move first. On your turn you may move to any of the eight squares adjacent to your current square, or stay where you are. On the mummies' turn, each mummy independently moves to the one adjacent square (among its eight neighbours) that minimizes its Euclidean distance to you — equivalently, every mummy shrinks the gap by one along each axis on which it is not already aligned with you. Two mummies may occupy the same square.

A time step consists of your move followed by every mummy's move. A mummy catches you if it moves onto the square you occupy, or if you move onto a square occupied by a mummy. You play to survive as long as possible.

After how many time steps are you caught?

For instance, suppose four mummies start at $(-3, 5)$ , $(3, 4)$ , $(-6, -2)$ and $(1, -5)$ while you start at the origin. However you move, after four time steps the mummy that began at $(3, 4)$ reaches you, so the answer is $4$ .

Input

The input consists of several test cases. Each test case begins with an integer $n$ ( $0 \le n \le 10^5$ ), the number of mummies. Each of the next $n$ lines contains two integers $x$ and $y$ ( $|x| \le 10^6$ , $|y| \le 10^6$ ), the starting square of one mummy. Your own starting square is $(0, 0)$ , and no mummy starts there.

The last test case is followed by a line containing a single $-1$ .

Output

For each test case, print a line Case k: r, where $k$ is the test case number (starting from $1$ ) and $r$ is the maximum number of time steps you survive before being caught (that is, the total number of turns you get to take), or the word never if you can avoid capture forever.

Hint

Relax — after working this out you wake up safe in a hotel room. The furious mummies were only a dream. Or were they?

Examples3

Example 1

Input

Expected output

Case 1: 4
Case 2: never

Example 2
Input
```
1
5 5
-1
```
Expected output
```
Case 1: never
```
Example 3
Input
```
4
1 1
1 -1
-1 1
-1 -1
-1
```
Expected output
```
Case 1: 1
```