Assume the locations of any three villages are (x1, y1, z1), (x2, y2, z2) and (x3, y3, z3). The distance of the paths passing through any three villages are defined as

      D = d₁₂ + d₂₃, where d_ij = |x_i - x_j| + |y_i - y_j| + |z_i - z_j|.

   Determine the shortest path passing through the three closest villages.

Input

   The first line specifies the number of villages, N (where 3 <= N <= 10,000). Each of the following N lines specifies the location (x, y, z) of each village (where -1000 <= x, y, z <= 1000).

Output

   One line specifies the length of the shortest path passing through the three closest villages.

Examples