# The Cube

You are locked in "The Cube". It is a gigantic three-dimensional
structure made up of cubic rooms distributed in a three-dimensional
grid. Therefore, we can identify each room with its coordinates
$(x,y,z) \in \mathbb{Z}^3$. Two rooms that completely share a face are
connected. Hence, every room has six adjacents rooms. You need one
minute to move from a room to any adjacent room.

0.5 After some exploration, you have discovered a way out. You have
identified $n$ special rooms with coordinates $(x_i, y_i, z_i)$. You
know that at a certain moment an alarm will sound and an announcement of
which of the $n$ rooms is the exit will be broadcast. To maximize your
chances of survival, you will wait in a room that minimizes the average
time to reach a special room.

Can you compute the sum of times to reach every special room if you
place yourself in an optimal room?

0.5

::: center
![image](cube.eps){width="6.5cm"}
:::

## Input

Input consists of several cases, each with $n$, followed by $n$
different triplets $x_i$ $y_i$ $z_i$. Assume $1 \le n \le 10^5$ and that
the coordinates are natural numbers between 1 and $10^9$.

## Output

For every case, print the minimum sum of times to reach every special
room.

## Problem information

Author: Edgar Moreno

Generation: 2026-01-25T11:29:18.659Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
