#include<iostream>
#define maxn 51
using namespace std;
int map[maxn][maxn];
int lx[maxn],ly[maxn],slack[maxn];
bool vx[maxn],vy[maxn];
int cas,n,m;
int match[maxn];
int ans;
int dfs(int t)
{
int i;
vx[t]=1;
int tmp;
for(i=1;i<=n;i++)
{
if(!vy[i])
{
tmp=lx[t]+ly[i]-map[t][i];
if(tmp==0)
{
vy[i]=1;
if(match[i]==-1||dfs(match[i]))
{
match[i]=t;
return 1;
}
}
else if(slack[i]>tmp)
slack[i]=tmp;
}
}
return 0;
}
int KM()
{
int i,j;
memset(match,-1,sizeof(match));
for(i=1;i<=n;i++)
{
lx[i]=-10000000;
for(j=1;j<=n;j++)
{
if(lx[i]<map[i][j])
lx[i]=map[i][j];
}
}
memset(ly,0,sizeof(ly));
for(i=1;i<=n;i++)
{
memset(slack,0x3f,sizeof(slack));
while(1)
{
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
if(dfs(i))
break;
int d=10000000;
for(j=1;j<=n;j++)
if(!vy[j]&&d>slack[j])
d=slack[j];
for(j=1;j<=n;j++)
{
if(vx[j])
lx[j]-=d;
if(vy[j])
ly[j]+=d;
}
}
}
for(i=1;i<=n;i++)
{
if(match[i]!=-1)
ans+=map[match[i]][i];
}
return 0;
}