include<bits/stdc++.h>

using namespace std; const int N=101,inf=1e5+7; int d[N][N],l[N][N],dp[N][N],d0[N][N],l0[N][N]; int n,Q; bool check(int x){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { d0[i][j]=d[i][j],l0[i][j]=l[i][j]; } for(int k=1;k<=x;k++) { int i=k%n; for(int j=1;j<=n;j++) { if(j!=i&&d0[i][j]-1>=l0[i][j])d0[i][j]--; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { dp[i][j]=d0[i][j]; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(dp[i][j]>dp[i][k]+dp[k][j]) { dp[i][j]=dp[i][k]+dp[k][j]; } } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { ans+=dp[i][j]; } if(ans<=Q)return true; return false; } int main() { cin>>n>>Q; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>d[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>l[i][j]; } } int ans=0; int m=(n*n); int l=1,r=m; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) { ans=mid; r=mid-1; } else { l=mid+1; } } cout<<ans<<endl; return 0;

}