import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
    public static PrintWriter stdOut = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static final int N = 110;
    public static int[][] population = new int[N][N];
    public static long[][] f = new long[N][N];
    public static int[][] limit = new int[N][N];
    public static long n, q;
    public static long floyd() {
        long res = 0;
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++) res += f[i][j];
        return res;
    }
    public static boolean check(int x) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++) f[i][j] = population[i][j];
        long count = (long)x / n;
        long last = (long)x % n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                if(i < last) f[i][j] = Math.max(limit[i][j], f[i][j] - count - 1);
                else f[i][j] = Math.max(limit[i][j], f[i][j] - count);
                f[j][i] = f[i][j];
            }
        }
        return floyd() <= q;
    }
    public static void main(String[] args) throws IOException{
        String[] sp = stdIn.readLine().split(" ");
        n = Long.parseLong(sp[0]); q = Long.parseLong(sp[1]);
        for(int i = 0; i < n; i++) {
            sp = stdIn.readLine().split(" ");
            for(int j = 0; j < n; j++) {
                population[i][j] = Integer.parseInt(sp[j]);
            }
        }
        for(int i = 0; i < n; i++) {
            sp = stdIn.readLine().split(" ");
            for(int j = 0; j < n; j++) {
                limit[i][j] = Integer.parseInt(sp[j]);
                f[i][j] = limit[i][j];
            }
        }
        if(floyd() > q) {
            stdOut.println("-1"); stdOut.flush();
            System.exit(0);
        }
        int l = 0; int r = 10000000;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        stdOut.println(l);
        stdOut.flush();
    }
}