레이팅 미적용Yulia는 예카테린부르크(E\(ka- te\)rinburg)의 금속 처리 공장에서 일한다. 이 공장은 우랄산맥에서 채굴된 광석을 처리해 황동석, 백금, 금 같은 귀금속을 광석에서 추출한다. 매달 공장은 미가공(\(un- pr\)ocessed) 광석 \(n\)회분의 수송분을 받는다. Yulia는 이 수송분들(sh\(ip- me\)nts)을 유사성에 따라 두 그룹으로 나누어야 한다. 그런 다음 각 그룹은 공장의 두 광석 처리(p\(ro- ce\)ssing) 건물 중 한 곳으로 보내진다. 이 분할을 위해 Yulia는 먼저 수송분(sh\(ip- me\)nts) 쌍 \(1 \le i \le n\), \(1 \le j \le n\)마다 수치 거리 \(d\)(i, j)를 계산한다. 거리가 작을수록 수송분(sh\(ip- me\)nts) \(i\)와 \(j\)는 더 유사하다. 수송분들의 부분집합 \(S\) ⊆{1, . . . , n}에 대해, \(S\)의 불일치도 \(D\)를 부분집합 안의 수송분 쌍 사이 거리의 최댓값으로 정의한다. 즉 \(D\)(\(S\)) = max {i,j} }_{S{d}}^{i, j{)} 그런 다음 Yulia는 불일치도들(disp\(ar- it\)ies)의 합 \(D\)(\(A\)) + \(D\)(\(B\))가 최소가 되도록 수송분들을 두 부분집합 \(A\)와 \(B\)로 분할한다. 당신의 임무는 이 분할을 찾도록 그녀를 돕는 것이다.
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 수송분의 수를 나타내는 정수 \(n\) (\(1 \le n \le 200\))이 주어진다. 이어지는 \(n - 1\)개의 줄에는 거리 \(d\)(i, j)가 담겨 있다. 그중 \(i^{th}\)번째 줄에는 \(n - i\)개의 정수가 있고, 그 줄의 \(j^{th}\)번째 정수는 \(d\)(i, \(i + j\))의 값이다. 거리는 대칭이므로 \(d\)(j, i) = \(d\)(i, j)이고, 수송분에서 자기 자신까지의 거리는 0이다. 모든 거리는 0 이상 \(10^{9}\) 이하의 정수이다.
수송분들을 두 그룹으로 분할할 때 가능한 불일치도 합의 최솟값을 출력한다.
5
4 5 0 2
1 3 7
2 0
4
4
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3
15