Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0118 - 3 NEAREST VILLAGES

   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 = d12 + d23, where dij = |xi - xj| + |yi - yj| + |zi - zj|.

   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

stdin

stdout

1

9

0 0 1

0 0 2

0 0 3

0 0 4

0 0 6

0 0 8

0 0 7

0 0 9

0 0 10

2


Ավելացրեց.Հրանտ Հովհաննիսյան (ԳՏՏԿ)
Ամսաթիվ.2014-02-02
Ժամանակի սահմանափակումը.2s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Thailand Central Group A 2013.B

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.