#include<bits/stdc++.h>
using namespace std;
int n,P;
long long ans=1e9,m[105][105],l[105][105],p[105][105];
bool check(long long x){
	for(int i=1;i<=n;i++){
		long long t=x/n;
		if(x%n+1>i)t++;
		for(int j=1;j<=n;j++){
			p[i][j]=max(l[i][j],m[i][j]-t);
		} 
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
			}
		}
	}
	long long sum=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			sum+=p[i][j];
		}
	}
	return sum<=P;
}
int main(){
	cin>>n>>P;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>m[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>l[i][j];
		}
	}
	long long l=0,r=100005;
	while(l<=r){
		long long mid=(l+r)/2;
		if(check(mid)==1)ans=min(ans,mid),r=mid-1;
		else l=mid+1;
	}
	if(ans>100000)cout<<"-1";
	else cout<<ans;
}