题意：在每行上选一个点，每个点都要各自对应的代价，同时相邻两行的点要满足 |j-k|≤f(i,j)+f(i+1,k)。问最小代价是多少。
题解：
不难发现这是一道dp，状态转移方程如下$dp[i][j]=min\{dp[i-1][k]\}+t[i][j](|j-k|≤f(i,j)+f(i+1,k))$
然而如果直接进行转移是要T飞的
所以如何快速求$k$呢？
可以发现，$dp[i-1][k]$只会对一个区间的答案产生影响，而$dp[i][j]$的答案必定是一个区间中的最小值加上自己的时间
于是就是区间修改和区间查询了，之间上线段树
ps：因为$dp$数组每一行都会更新，实际上可以省掉第一维的空间
//minamoto
#include<cstdio>
#include<iostream>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=,M=,inf=0x3f3f3f3f;
int t[N][M],f[N][M],dp[M],sum[M<<],add[M<<];
int n,m;
void pushdown(int p){
if(add[p]!=inf){
cmin(add[p<<],add[p]),cmin(add[p<<|],add[p]);
cmin(sum[p<<],add[p<<]),cmin(sum[p<<|],add[p<<|]);
add[p]=inf;
}
}
void build(int l,int r,int p){
sum[p]=add[p]=inf;
if(l==r) return;
int mid=l+r>>;
build(l,mid,p<<),build(mid+,r,p<<|);
}
void update(int ql,int qr,int x,int l,int r,int p){
if(ql<=l&&qr>=r){
cmin(add[p],x),cmin(sum[p],add[p]);return;
}
int mid=l+r>>;
pushdown(p);
if(ql<=mid) update(ql,qr,x,l,mid,p<<);
if(qr>mid) update(ql,qr,x,mid+,r,p<<|);
sum[p]=min(sum[p<<],sum[p<<|]);
}
int query(int ql,int qr,int l,int r,int p){
if(ql<=l&&qr>=r) return sum[p];
int mid=l+r>>;
pushdown(p);
int res=inf;
if(ql<=mid) cmin(res,query(ql,qr,l,mid,p<<));
if(qr>mid) cmin(res,query(ql,qr,mid+,r,p<<|));
return res;
}
int main(){
//freopen("testdata.in","r",stdin);
while(true){
n=read(),m=read();
if(n==&&m==) break;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
t[i][j]=read();
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
f[i][j]=read();
for(int i=;i<=m;++i) dp[i]=t[][i];
for(int i=;i<=n;++i){
build(,m,);
for(int j=;j<=m;++j)
update(j-f[i-][j],j+f[i-][j],dp[j],,m,);
for(int j=;j<=m;++j)
dp[j]=query(j-f[i][j],j+f[i][j],,m,)+t[i][j];
}
int ans=inf;
for(int i=;i<=m;++i) cmin(ans,dp[i]);
print(ans);
}
Ot();
return ;
}