dp[i][j]表示在第i时经过第j-1条马路走到第j个工厂收集到的金币最大值

#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int a[1005][1005],v[1005];
long long dp[1005][1005];
int main()
{
	cin>>n>>m>>p;
	memset(dp,-0x7f,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		dp[0][i]=0;
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			long long sum=0;
			for(int k=1;k<=min(i,p);k++)
			{
				int st=(j-k)%n;
				while(st<=0)st+=n;
				sum+=a[st][i-k+1];
				dp[i][j]=max(dp[i][j],dp[i-k][st]+sum-v[st]);
			}
		//	cout<<dp[i][j]<<" ";
		} 
	//	cout<<endl;
	}
	long long ans=INT_MIN;
	for(int i=1;i<=n;i++)ans=max(ans,dp[m][i]);
	cout<<ans;
}