The Cube P66524

Statement

thehtml

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) ∈ ℤ³. 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.

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?

Input

Input consists of several cases, each with n, followed by n different triplets x_i y_i z_i. Assume 1 ≤ n ≤ 10⁵ and that the coordinates are natural numbers between 1 and 10⁹.

Output

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

Public test cases

Input

1  23 42 100
2  1 1 1  10 20 30
4  1 1 1000000000  1 1000000000 1  1000000000 1 1  999999999 999999998 999999997

Output

0
57
5999999988

Information

Author: Edgar Moreno
Language: English
Official solutions: C++
User solutions: C++