题意：有n行路，每行路被分成m段，每一段有长度和权值，要求从最下面一行走到最上面一行某个位置，可以从相邻两行的同一列交点往上走，并且在同一行走的长度要<=K，求走过的最大权值
设f[i][j]为到第i行，第j个交点的最大值
设sumvalue[i][j,k]为第i行从第j个交点到第k个交点经过道路的权值之和
设sumtime[i][j,k]为第i行从第j个交点到第k个交点经过道路的长度之和
则f[i][j]=max{
f[i-1][k]+sumvalue[i][k,j] ,k<=j且sumtime[i][k,j]<=K
f[i-1][k]+sumvalue[i][j,k] ,k>j且sumtime[i][j,k]<=K
}
以第一个方程为例，单调队列记某行i∈[k,j]的f[][i]+sumvalue[][i..j]的最大值即可
其中，在j++的时候，由于要给所有数加上val[][j]的值，我们就假装大家一起
减掉了val[][j]的值，只给要新进的f[][j]+val[][j]减掉sumvalue[][0..j]即可
（最后给f值的时候别忘了加回来）
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn=,maxm=; int rd(){
int x=,neg=;char c=getchar();
while(c<''||c>'') {if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,K;
int val[maxm][maxn],len[maxm][maxn],head,tail;
LL f[maxm][maxn],q[maxm][],ans; inline void insert(LL x,int y){
for(int i=tail;i>=head;i--){
if(q[i][]>x){
tail=i+;q[tail][]=x;q[tail][]=y;
return;
}
}tail=head;q[tail][]=x;q[tail][]=y;
} int main(){
int i,j,k;
//freopen("3926.in","r",stdin);
while(){
N=rd(),M=rd(),K=rd();if(!N) break;
for(i=;i<=N+;i++){
for(j=;j<=M;j++) val[j][i]=rd();
}for(i=;i<=N+;i++){
for(j=;j<=M;j++) len[j][i]=rd();
}
memset(f,,sizeof(f));ans=;
for(i=;i<=N+;i++){
LL sv=,st=;
tail=head=;memset(q,,sizeof(q));
for(j=;j<=M;j++){
sv+=val[j][i],st+=len[j][i];
insert(f[j][i-]-sv,st);
while(st-q[head][]>K) head++;
f[j][i]=q[head][]+sv;
}
sv=;st=;
tail=head=;memset(q,,sizeof(q));
for(j=M;j>=;j--){
sv+=val[j+][i],st+=len[j+][i];
insert(f[j][i-]-sv,st);
while(st-q[head][]>K) head++;
f[j][i]=max(f[j][i],q[head][]+sv);
}
}
for(j=;j<=M;j++) ans=max(ans,f[j][N+]);
printf("%d\n",ans);
} }