P16777 [GKS 2020 #H] Rugby

On a far away planet, rugby is played in the $2$-dimensional Cartesian coordinate system without bounds. The players can occupy integer grid points only and they can move to the neighboring grid points in any of the $4$ cardinal directions. Specifically, if a player is currently at the point $(X, Y)$, then they can move to either of the points $(X+1, Y)$, $(X-1, Y)$, $(X, Y+1)$, or $(X, Y-1)$ in a single step. After the game, $N$ players are scattered throughout the coordinate system such that any grid point is empty or occupied by $1$ or more players. They want to gather for a picture and form a perfect horizontal line of $N$ grid points, $1$ player per point, all occupied points next to each other. Formally, the players have to move so as to occupy the grid points $(X, Y)$, $(X+1, Y)$, $(X+2, Y)$, ..., $(X+N-1, Y)$ for some coordinates $X$ and $Y$. What is the minimum total number of steps the players should make to form a perfect line if they are free to choose the position of the line in the coordinate system and the ordering of players is not important?

The first line of the input gives the number of test cases $T$. $T$ test cases follow. The first line of each test case gives the number of players $N$. The subsequent $N$ lines give the initial coordinates of the players. The $i$-th of these lines contains $2$ integers $X_i$ and $Y_i$, which describe the initial position of the $i$-th player ($1 \le i \le N$).

For each test case, output one line containing Case $\#x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the minimum total number of steps that the players need to make in order to form a perfect horizontal line.

In the $1$st test case, $1$ of many optimal solutions is obtained by the $2$nd player moving $2$ steps to the left and $3$ steps down to the point $(2, 1)$. In the $2$nd test case, a perfect line can be formed with a total of $4$ steps if the $1$st player moves to the point $(0, 2)$ and the $3$rd player moves to the point $(2, 2)$. ### Limits **Test Set $1$** $1 \le N \le 10$. $-500 \le X_i \le 500$. $-500 \le Y_i \le 500$. **Test Set $2$** $1 \le N \le 10^5$ for at most $10$ cases. $1 \le N \le 10^4$ for the remaining cases. $-10^9 \le X_i \le 10^9$. $-10^9 \le Y_i \le 10^9$.