https://www.luogu.com.cn/record/221399828

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int e[110][110];
int e1[110][110],enow[110][110];
int n,Q;
bool check(int day)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			enow[i][j] = e[i][j];
		}
	}
	int sum = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			enow[i][j] = max(e1[i][j],enow[i][j]-(day/n)-(day%n>=i?1:0));
			enow[j][i] = max(e1[j][i],enow[j][i]-(day/n)-(day%n>=i?1:0));
			//cout << enow[i][j] << ' '; 
		}
		//cout << endl;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				enow[i][j] = min(enow[i][j],enow[i][k] + enow[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			sum += enow[i][j];
		}
	}
	//cout << sum << endl;
	return sum <= Q;
}
signed main()
{
	cin >> n >> Q;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin >> e[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin >> e1[i][j];
		}
	}
	int l=0,r=n*10000000;
	int day,ans=-1;
	while(l < r)
	{
		day = (l+r)>>1;
		if(check(day)) r=day-1,ans=day;
		else l=day+1;
		//cout << day << endl;
	}
	//cout << endl;
	cout << ans;
	return 0;
}