题意：有 (n) 个元素，第 (i) 个数与第 (j) 个数之间有一个权值 (d_{i,j})，(d(i,j)=d(j,i))。
定义函数 (D(S)=maxlimits_{i in S,j in S,i eq j}d(i,j))。
现在你要将 (n) 个元素划分为两个集合 (A,B)，求 (min{D(A)+D(B)})。
(1 leq n leq 200)。
第一道 ACM World Final，祭一个。
看到这种非黑即白的问题，自然可以想到 2-SAT 啦。
很显然的思路是，不妨设 (D(A)>D(B))，枚举 (D(A)) 可能的值，二分 (D(B)) 的值，用 2-SAT 判定合法性，对于每个 (d(i,j)>D(A))，如果 (i in A)，那么 (j
otin A)，(D(B)) 也同理。
不过这样是 (n^4 log n) 的，因此需要优化。
我们将每个 ((i,j)) 看做一条边，边权为 (d(i,j))，那么我们将边权从大到小排序，并顺次加边。
如果加入边权为 (x) 的边之后，图出现了奇数环，那么处理完 (x) 之后直接退出，因为我们无法对边权 (geq x) 的进行黑白染色，使得同一条边两个端点颜色不同。
同理，如果加入边权为 (x) 的边之后，图出现了偶数环，那么这条边一定不能是 (A) 中边权最大的边。因为如果它是 (A) 中边权最大的边，那么它的两个端点颜色相同，可以看作一个点，偶数环变成了奇数环，显然是不满足条件的。
这样一来，我们最多只会加入 (n-1) 条树边，时间复杂度就降到了 (n^3 log n) 了。
坑点：特判 (n leq 2) 答案为 (0)，我为此不停地 WA 3，然后发现 test 3 (n=1)？
//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a) (1ll<<(a))
#define maskx(a,x) ((a)<<(x))
#define _bit(a,x) (((a)>>(x))&1)
#define _sz(a) ((int)(a).size())
#define filei(a) freopen(a,"r",stdin);
#define fileo(a) freopen(a,"w",stdout);
#define fileio(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x) putchar(x)
#define eoln put('
')
#define space put(' ')
#define y1 y_chenxiaoyan_1
#define y0 y_chenxiaoyan_0
#define int long long
typedef pair<int,int> pii;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') neg=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*neg;
}
inline void print(int x){
if(x<0){
putchar('-');
print(abs(x));
return;
}
if(x<=9) putchar(x+'0');
else{
print(x/10);
putchar(x%10+'0');
}
}
inline int qpow(int x,int e,int _MOD){
int ans=1;
while(e){
if(e&1) ans=ans*x%_MOD;
x=x*x%_MOD;
e>>=1;
}
return ans;
}
struct edge{
int u,v,w;
edge(){/*ycxakioi*/}
edge(int _u,int _v,int _w){
u=_u;v=_v;w=_w;
}
friend bool operator <(edge a,edge b){
return a.w<b.w;
}
} e[40005];
int n=read(),cnt=0;
int f[405],col[405],siz[405];
inline int find(int x){
return (f[x]==x)?x:find(f[x]);
}
inline int getc(int x){
return (f[x]==x)?0:(getc(f[x])^col[x]);
}
vector<int> g[405];
int dfn[405],idx=0,low[405],stk[405],top,comp,bel[405],vis[405];
inline void tarjan(int x){
dfn[x]=low[x]=++idx;stk[++top]=x;vis[x]=1;
foreach(it,g[x]){
int y=*it;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
comp++;
while(top){
int y=stk[top--];
vis[y]=0;
bel[y]=comp;
if(y==x) break;
}
}
}
inline bool _2_SAT(int mn1,int mn2){
fill0(dfn);fill0(low);fill0(stk);fill0(vis);fill0(bel);
comp=top=idx=0;
fz(i,0,404) g[i].clear();
fz(i,1,cnt){
if(e[i].w>mn1) g[e[i].u*2-1].push_back(e[i].v*2),g[e[i].v*2-1].push_back(e[i].u*2);
if(e[i].w>mn2) g[e[i].u*2].push_back(e[i].v*2-1),g[e[i].v*2].push_back(e[i].u*2-1);
}
fz(i,1,n*2) if(!dfn[i]) tarjan(i);
fz(i,1,n) if(bel[i*2-1]==bel[i*2]) return 0;
return 1;
}
signed main(){
fz(i,1,n) fz(j,i+1,n){
int t=read();
e[++cnt].u=i;
e[cnt].v=j;
e[cnt].w=t;
}
if(n<=2) return puts("0"),0;
sort(e+1,e+cnt+1);
fz(i,1,n*2) f[i]=i,siz[i]=1;
int ans=INT_MAX;
fd(i,cnt,1){
int x=e[i].u,y=e[i].v,z=e[i].w;
int xx=find(x),yy=find(y);
if(xx!=yy){
if(siz[xx]<siz[yy]) swap(x,y),swap(xx,yy);
if(getc(x)==getc(y)) col[yy]^=1;
f[yy]=xx;
siz[xx]+=siz[yy];
}
else if(getc(x)!=getc(y)) continue;
int l=0,r=i-1,anss=0x3f3f3f3f;
while(l<=r){
int mid=(l+r)>>1;
if(_2_SAT(e[i].w,e[mid].w)) anss=e[mid].w,r=mid-1;
else l=mid+1;
}
ans=min(ans,e[i].w+anss);
if(getc(x)==getc(y)) break;
}
cout<<ans<<endl;
return 0;
}