# h901 Java solution

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

解法 : 二分搜答案，用匈牙利演算法作二分匹配

/* 
 sometimes you have to accept the fact that there's always a Penguin07
 dianer than u and you're so weak because hey that's how life works.
 It may sounds unfair but one day your time will come. you will become so
 dian like Penguin07 and you will be happy for 5 seconds and move on with
 your life. It's that easy. come on now, let's all go to sleep.
*/
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main {
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static long ret;
	public static int reti,rd;
	public static boolean neg;
	public static final int mod=998244353;
	public static final int mod2=1_000_000_007;
	public static final int maxn=305;
	public static Useful us=new Useful(mod2);
	public static long[][] u=new long[maxn][maxn];
	public static long[][] v=new long[maxn][maxn];
	public static long[][] c=new long[maxn][maxn];
	public static int[] vis=new int[maxn];
	public static int[] mat=new int[maxn];
	public static ArrayList<ArrayList<Integer>> e=new ArrayList<>();
	public static void main(String[] args) throws Exception{
		final int n=readint();
		final int k=readint();
		for(int i=0;i<n;i++) {
			for(int j=0;j<k;j++) {
				u[i][j]=readint();
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<k;j++) {
				v[i][j]=readint();
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				for(int p=0;p<k;p++) {
					c[i][j]+=u[i][p]*v[j][p];
				}
			}
		}
		long L=1,R=(long)Math.pow(10,16),M;
		while(L!=R) {
			M=(L+R)>>1;
			e=new ArrayList<>();
			us.arr(mat,-1);
			us.arr(vis,-1);
			for(int i=0;i<n;i++) {
				e.add(new ArrayList<>());
				for(int j=0;j<n;j++) {
					if(c[i][j]<=M) {
						e.get(i).add(j);
					}
				}
			}
			int cnt=0;
			for(int i=0;i<n;i++) {
				cnt+=Hungarian(i,i);
			}
			if(cnt==n) {
				R=M;
			}
			else {
				L=M+1;
			}
		}
		System.out.println(L);
	}
	
	public static int Hungarian(int x,int y){
		if(vis[x]==y)return 0;
	    vis[x]=y;
		for(int i:e.get(x)){
			if((mat[i]==-1)||(Hungarian(mat[i],y)==1)){
				mat[i]=x;
				return 1;
			}
		}
		return 0;
	}
	
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
}
/*

 */

/*

 */

class Pii{
	int rev,x,y;
	Pii(int r,int a,int b){
		rev=r;
		x=a;
		y=b;
	}
}

class Pll{
	long x,y;
	Pll(long a,long b){
		x=a;
		y=b;
	}
}

class Useful{
	long mod;
	Useful(long m){mod=m;}
	void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
	void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	long fast(long x,long pw) {
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long[][] mul(long[][] a,long[][] b){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}

	long[][] fast(long[][] x,int pw){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1);
		if((pw&1)==0) {
			return mul(h,h);
		}
		else {
			return mul(mul(h,h),x);
		}
	}
	int gcd(int a,int b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long gcd(long a,long b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long lcm(long a, long b){
	    return a*(b/gcd(a,b));
	}
	double log2(int x) {
		return (Math.log(x)/Math.log(2));
	}
	double log2(long x) {
		return (Math.log(x)/Math.log(2));
	}
}