#include<bits/stdc++.h>

using namespace std;
using LL = long long;

int n;
LL q;
LL hui[111][111];
LL xia[111][111];

LL fl(LL t)
{
	LL dp[111][111];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = hui[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = dp[j][i] = max(dp[i][j] - t / n - (t % n >= i  ? 1 : 0), xia[i][j]);
		}
	}



	for (int i = 1; i <= n; i++) { 
		for (int j = 1; j <= n; j++) {
			for (int z = 1; z <= n; z++) {
				dp[j][z] = min(dp[j][z], dp[j][i] + dp[i][z]);
			}
		}
	}




	LL s = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			s += dp[i][j];
		}
	}

//	cout << t << " " << s << endl;

	return s;
}


void solve()
{
	cin >> n >> q;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cin >> hui[i][j];
	}

	LL s = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> xia[i][j];
			s += xia[i][j];
		}
	}

	if (s > q)
	{
		cout << "-1" << endl;
		return;
	}

	LL l = -1, r = 100001 * n;

	while (l + 1 < r)
	{
		LL mid = (l + r) / 2;
		if (fl(mid) > q) l = mid;
		else r = mid;
	}

	cout << r << endl;


}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//srand(time(nullptr));


	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}

	return  0;
}