namespace KM
{
constexpr int Na=510;
int N,res,p,q,id,val,d[Na][Na];
int vis[Na],match[Na],pre[Na],slack[Na],lx[Na],ly[Na];
inline void Augment(int s)
{
match[0]=s,p=q=id=val=0;
fill(pre+1,pre+N+1,0),fill(slack+1,slack+N+1,INF),fill(vis+1,vis+N+1,0);
while(match[q])
{
p=match[q=id],vis[q]=1,val=INF;
for(int i=1;i<=N;++i) if(!vis[i])
{
if(slack[i]>lx[p]+ly[i]-d[p][i]) slack[i]=lx[p]+ly[i]-d[p][i],pre[i]=q;
if(slack[i]<val) val=slack[id=i];
}
for(int i=0;i<=N;++i) if(vis[i]) lx[match[i]]-=val,ly[i]+=val; else slack[i]-=val;
}
for(;q;q=pre[q]) match[q]=match[pre[q]];
}
inline void Work()
{
for(int i=1;i<=N;++i)
{
lx[i]=-INF,ly[i]=0;
for(int j=1;j<=N;++j) cmax(lx[i],d[i][j]);
}
for(int i=1;i<=N;++i) Augment(i);
for(int i=1;i<=N;++i) res+=lx[i]+ly[i];
}
}