Board Meeting

Note that it is not necessary to know anything about the rules of chess to solve this problem.

There are $N$ kings on an infinite chessboard (a two-dimensional grid), located in cells with coordinates $(X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N)$. Neither $N$ nor the kings' coordinates are known to you. You do know the following:

• $N$ is at least 1 and at most $N_{\max}$.
• No king's coordinates ($X$ or $Y$) have an absolute value exceeding $M$.
• The $N$ kings occupy $N$ different cells.

The kings want to meet in a single cell of the board. If cell $(X, Y)$ is chosen as the meeting cell, the $i$-th king needs $\max(|X-X_i|, |Y-Y_i|)$ moves to get there. The total number of moves is the sum of these values over all $i$. The exact path each king takes does not matter. Only the start and end cells matter, and the move count can always be computed with the formula above.

• $1 \le T \le 15$.
• $M = 10^6$.
• $-M \le X_i \le M$ for all $i$.
• $-M \le Y_i \le M$ for all $i$.
• The pairs $(X_i, Y_i)$ are distinct.
• $-10 \times M \le C_i \le 10 \times M$ for all $i$.
• $-10 \times M \le D_i \le 10 \times M$ for all $i$.
• $R = 1000$.