#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,u[305],v[305],w[305][305]; struct qry { int a,b,c,d,id; qry(int _a,int _b,int _c,int _d,int _id){a=_a,b=_b,c=_c,d=_d,id=_id;} }; void sol2(int l1,int r1,int l2,int r2,vector<qry>&Q); ll f[305][305],g[305][305],h[305][305]; ll F[305][305],G[305][305],H[305][305]; ll res[maxn]; struct nd { int x,y,op; nd(){} nd(int _x,int _y,int _op){x=_x,y=_y,op=_op;} }; void ZY1(int l1,int l2,int r1,int r2,int op){ assert(l1<=r1&&l2<=r2); up(i,l1,r1)up(j,l2,r2)f[i][j]=g[i][j]=h[i][j]=-1e18; if(op==0)f[l1][l2]=0; else if(op==1)g[l1][l2]=0; else h[l1][l2]=0; up(i,l1,r1){ up(j,l2,r2){ if(i-1>=l1)f[i][j]=max(f[i][j],f[i-1][j]); if(j-1>=l2)f[i][j]=max(f[i][j],f[i][j-1]); if(i-1>=l1)f[i][j]=max(f[i][j],g[i-1][j]); if(j-1>=l2)f[i][j]=max(f[i][j],h[i][j-1]); g[i][j]=max(g[i][j],f[i][j]-u[i]); if(j-1>=l2)g[i][j]=max(g[i][j],g[i][j-1]+max(-v[j-1]+w[i][j-1],0)); if(j-1>=l2)g[i][j]=max(g[i][j],h[i][j-1]-u[i]+w[i][j-1]); h[i][j]=f[i][j]-v[j]; if(i-1>=l1)h[i][j]=max(h[i][j],h[i-1][j]+max(-u[i-1]+w[i-1][j],0)); if(i-1>=l1)h[i][j]=max(h[i][j],g[i-1][j]-v[j]+w[i-1][j]); //printf("f[%d][%d]=%lld\n",i,j,f[i][j]); //printf("g[%d][%d]=%lld\n",i,j,g[i][j]); //printf("h[%d][%d]=%lld\n",i,j,h[i][j]); } } } void ZY2(int l1,int l2,int r1,int r2,int op){ assert(l1<=r1&&l2<=r2); up(i,l1,r1)up(j,l2,r2)F[i][j]=G[i][j]=H[i][j]=-1e18; if(op==0)F[r1][r2]=0; else if(op==1)G[r1][r2]=0; else H[r1][r2]=0; down(i,r1,l1){ down(j,r2,l2){ F[i][j]=max(F[i][j],G[i][j]-u[i]); F[i][j]=max(F[i][j],H[i][j]-v[j]); if(i-1>=l1)F[i-1][j]=max(F[i-1][j],F[i][j]); if(j-1>=l2)F[i][j-1]=max(F[i][j-1],F[i][j]); if(i-1>=l1)G[i-1][j]=max(G[i-1][j],F[i][j]); if(j-1>=l2)H[i][j-1]=max(H[i][j-1],F[i][j]); if(j-1>=l2)G[i][j-1]=max(G[i][j-1],G[i][j]+max(-v[j-1]+w[i][j-1],0)); if(j-1>=l2)H[i][j-1]=max(H[i][j-1],G[i][j]-u[i]+w[i][j-1]); if(i-1>=l1)H[i-1][j]=max(H[i-1][j],H[i][j]+max(-u[i-1]+w[i-1][j],0)); if(i-1>=l1)G[i-1][j]=max(G[i-1][j],H[i][j]-v[j]+w[i-1][j]); } } } void sol(int l1,int r1,int l2,int r2,vector<qry>&Q){ if(l1>r1||l2>r2) return; int mid=l1+r1>>1; vector<qry>Q1,Q2,Q3; for(auto it:Q){ if(it.a<=mid&&it.b>=mid)Q1.p_b(it); else if(it.b<mid)Q2.p_b(it); else Q3.p_b(it); } if(Q1.size()){ up(i,l2,r2){ up(o,0,2){ ZY1(mid,i,r1,r2,o); ZY2(l1,l2,mid,i,o); for(auto it:Q1){ if(it.c>i||it.d<i)continue; ll val=F[it.a][it.c]+f[it.b][it.d]; res[it.id]=max(res[it.id],val); } } } } sol2(l1,mid-1,l2,r2,Q2); sol2(mid+1,r1,l2,r2,Q3); } void sol2(int l1,int r1,int l2,int r2,vector<qry>&Q){ if(l1>r1||l2>r2) return; int mid=l2+r2>>1; vector<qry>Q1,Q2,Q3; for(auto it:Q){ if(it.c<=mid&&it.d>=mid)Q1.p_b(it); else if(it.c<mid)Q2.p_b(it); else Q3.p_b(it); } if(Q1.size()){ up(i,l1,r1)up(o,0,2){ ZY1(i,mid,r1,r2,o); ZY2(l1,l2,i,mid,o); for(auto it:Q1){ if(it.a>i||it.b<i)continue; ll val=F[it.a][it.c]+f[it.b][it.d]; //printf("! %lld\n",val); res[it.id]=max(res[it.id],val); } } } sol(l1,r1,l2,mid-1,Q2); sol(l1,r1,mid+1,r2,Q3); } void slv(){ n=read(),q=read(); up(i,1,n)u[i]=read();up(i,1,n)v[i]=read(); up(i,1,n)up(j,1,n)w[i][j]=read(); //ZY1(1,2,2,4); //cout<<"? "<<f[2][4]<<endl; //ZY1(1,2,3,4,0); //cout<<"? "<<f[3][4]<<endl; //ZY2(1,2,3,4,0); //cout<<"? "<<F[1][2]<<endl; vector<qry>v; up(i,1,q){ int a=read(),b=read()+1,c=read(),d=read()+1; v.p_b(qry(a,b,c,d,i)); } sol(1,n+1,1,n+1,v); up(i,1,q)printf("%lld\n",res[i]); }int main(){ //freopen("1.in","r",stdin),freopen("1.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }