cho.sh

Metal Processing Plant

No attempts yetTime limit4sMemory limit128 MB

Problem

Each month n ore shipments arrive. Pairwise distances d(i,j) measure similarity. For a subset S, define

D(S) = max_{i,j in S} d(i,j)

(zero when |S| ≤ 1). Partition all shipments into two groups A and B to minimize D(A) + D(B).

Input

  • Line 1: integer n (1 ≤ n ≤ 200)
  • Next n-1 lines: line i lists d(i,i+1) through d(i,n)

Output

The minimum possible value of D(A) + D(B)