#include <iostream>
#include <algorithm>

using namespace std;

const int N = 101;

int n, q, s, a[N][N], d[N][N], l[N][N];

bool check(int m) {
    int t = m / n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = max(l[i][j], a[i][j] - t);
            d[j][i] = max(l[j][i], a[j][i] - t);
        }
    }
    t = m % n;
    for (int i = 0; i < t; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) {
                d[i][j] = max(d[i][j] - 1, l[i][j]);
                d[j][i] = max(d[j][i] - 1, l[j][i]);
            }
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (i == k) continue;
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int p = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            p += d[i][j];
        }
    }
    return p <= q;
}

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> l[i][j];
        }
    }
    int l = 1, r = 1e9, res = -1;
    while (l <= r) {
        int m = l + r >> 1;
        if (check(m)) r = m - 1, res = m;
        else l = m + 1;
    }
    cout << res;
    return 0;
}