int g[maxn][maxn],linker[maxn];
bool used[maxn];
bool dfs(int u){
	for(int i=0;i<m;i++){
		if(g[u][i] && !used[i]){
			used[i]=true;
			if(linker[i]==-1 || dfs(linker[i])){
				linker[i]=u;
				return true;
			}
		}
	}
	return false;
}
int hungary(){
	int ans=0;
	mm(linker,-1);
	for(int i=0;i<n;i++){
		mm(used,0);
		if(dfs(i)) ans++;
	}
	return ans;
}

int nx,ny;
int g[maxn][maxn];
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];
bool dfs(int x){
	visx[x]=true;
	for(int y=0;y<ny;y++){
		if(visy[y]) continue;
		int tmp=lx[x]+ly[y]-g[x][y];
		if(tmp==0){
			visy[y]=true;
			if(linker[y]==-1 || dfs(linker[y])){
				linker[y]=x;
				return true;
			}
		}
		else slack[y]=min(slack[y],tmp);
	}
	return false;
}
int km(){
	mm(linker,-1),mm(ly,0);
	for(int i=0;i<nx;i++){
		lx[i]=g[i][0];
		for(int j=1;j<ny;j++) lx[i]=max(lx[i],g[i][j]);
	}
	for(int i=0;i<nx;i++){
		fill(slack,slack+ny,inf);
		while(1){
			mm(visx,false),mm(visy,false);
			if(dfs(i)) break;
			int d=inf;
			for(int j=0;j<ny;j++){
				if(!visy[j]) d=min(d,slack[j]);
			}
			for(int j=0;j<nx;j++){
				if(visx[j]) lx[j]-=d;
			}
			for(int j=0;j<ny;j++){
				if(visy[j]) ly[j]+=d;
				else slack[j]-=d;
			}
		}
	}
	int ans=0;
	for(int i=0;i<ny;i++){
		if(linker[i]!=-1) ans+=g[linker[i]][i];
	}
	return ans;
}