Problem Statement

In a three-dimensional space, there are $N$ cities: City $1$ through City $N$. City $i$ is at point $(X_i,Y_i,Z_i)$.

The cost it takes to travel from a city at point $(a,b,c)$ to a city at point $(p,q,r)$ is $|p-a|+|q-b|+\max(0,r-c)$.

Find the minimum total cost it takes to start at City $1$, visit all other cities at least once, and return to City $1$.

Constraints

• $2 \leq N \leq 17$
• $-10^6 \leq X_i,Y_i,Z_i \leq 10^6$
• No two cities are at the same point.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 Z_1
\vdots
X_N Y_N Z_N

Output

Print the minimum total cost it takes to start at City $1$, visit all other cities at least once, and return to City $1$.