#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool memBeg;
template<typename T,typename TT> void chkmin(T &x,TT y) {if(x>y) x=y;}
template<typename T,typename TT> void chkmax(T &x,TT y) {if(x<y) x=y;}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,ll times,int ret=1) {
    for(;times;times>>=1,x=1ll*x*x%mod) if(times&1) ret=1ll*ret*x%mod;
    return ret;
}
constexpr int maxn=505;
constexpr int maxQ=3e5+5;
constexpr int inf=0x3f3f3f3f;
int n,Q,c1[maxn],c2[maxn],mat[maxn][maxn],qa[maxQ],qb[maxQ],qc[maxQ],qd[maxQ],ret[maxQ];
int lhs[maxn][maxn][2][2],rhs[maxn][maxn][2][2],qry[maxQ];
void clhs(int l1,int r1,int l2,int r2,int tp) {
    lhs[r1+1][r2+1][0][0]=lhs[r1+1][r2+1][0][1]=0;
    lhs[r1+1][r2+1][1][0]=lhs[r1+1][r2+1][1][1]=0;
    lhs[r1+1][r2][0][0]=0; lhs[r1+1][r2][0][1]=-inf;
    lhs[r1+1][r2][1][0]=0; lhs[r1+1][r2][1][1]=-inf;
    lhs[r1][r2+1][0][0]=lhs[r1][r2+1][0][1]=0;
    lhs[r1][r2+1][1][0]=lhs[r1][r2+1][1][1]=-inf;
    // printf("l1 = %d, r1 = %d, l2 = %d, r2 = %d, tp = %d\n",l1,r1,l2,r2,tp);
    for(int i=r1;i>=l1;i--) {
        for(int j=r2;j>=l2;j--) {
            for(int a=1;a>=0;a--) {
                for(int b=1;b>=0;b--) {
                    lhs[i][j][a][b]=-inf;
                    if(!a) chkmax(lhs[i][j][a][b],lhs[i][j][1][b]);
                    if(!b) chkmax(lhs[i][j][a][b],lhs[i][j][a][1]);
                    if(tp==1&&i==r1&&!a) continue;
                    if(tp==2&&j==r2&&!b) continue;
                    if(!a) chkmax(lhs[i][j][a][b],lhs[i+1][j][0][b]);
                    if(!b) chkmax(lhs[i][j][a][b],lhs[i][j+1][a][0]);
                    if(a&&b) {
                        chkmax(lhs[i][j][a][b],lhs[i+1][j][0][1]+mat[i][j]-c1[i]);
                        chkmax(lhs[i][j][a][b],lhs[i][j+1][1][0]+mat[i][j]-c2[j]);
                        chkmax(lhs[i][j][a][b],lhs[i+1][j+1][0][0]+mat[i][j]-c1[i]-c2[j]);
                    }
                    // printf("lhs[i = %d][j = %d][a = %d][b = %d] = %d\n",i,j,a,b,lhs[i][j][a][b]);
                }
            }
        }
    }
}
void crhs(int l1,int r1,int l2,int r2,int tp) {
    rhs[l1-1][l2-1][0][0]=rhs[l1-1][l2-1][0][1]=0;
    rhs[l1-1][l2-1][1][0]=rhs[l1-1][l2-1][1][1]=0;
    rhs[l1][l2-1][0][0]=rhs[l1][l2-1][0][1]=0;
    rhs[l1][l2-1][1][0]=rhs[l1][l2-1][1][1]=-inf;
    rhs[l1-1][l2][0][0]=0; rhs[l1-1][l2][0][1]=-inf;
    rhs[l1-1][l2][1][0]=0; rhs[l1-1][l2][1][1]=-inf;
    // printf("l1 = %d, r1 = %d, l2 = %d, r2 = %d, tp = %d\n",l1,r1,l2,r2,tp);
    int t=-1;
    if(tp==1) t=c1[l1],c1[l1]=0;
    if(tp==2) t=c2[l2],c2[l2]=0;
    for(int i=l1;i<=r1;i++) {
        for(int j=l2;j<=r2;j++) {
            for(int a=1;a>=0;a--) {
                for(int b=1;b>=0;b--) {
                    rhs[i][j][a][b]=-inf;
                    if(!a) {
                        chkmax(rhs[i][j][a][b],rhs[i-1][j][0][b]);
                        chkmax(rhs[i][j][a][b],rhs[i][j][1][b]);
                    }
                    if(!b) {
                        chkmax(rhs[i][j][a][b],rhs[i][j-1][a][0]);
                        chkmax(rhs[i][j][a][b],rhs[i][j][a][1]);
                    }
                    if(a&&b) {
                        chkmax(rhs[i][j][a][b],rhs[i-1][j][0][1]+mat[i][j]-c1[i]);
                        chkmax(rhs[i][j][a][b],rhs[i][j-1][1][0]+mat[i][j]-c2[j]);
                        chkmax(rhs[i][j][a][b],rhs[i-1][j-1][0][0]+mat[i][j]-c1[i]-c2[j]);
                    }
                    // printf("rhs[i = %d][j = %d][a = %d][b = %d] = %d\n",i,j,a,b,rhs[i][j][a][b]);
                }
            }
        }
    }
    if(tp==1) c1[l1]=t;
    if(tp==2) c2[l2]=t;
}
void solve(int l1,int r1,int l2,int r2,int *stk,int top) {
    if(!top) return;
    if(l1==r1&&l2==r2) {
        int mx=max(0,-c1[l1]-c2[l2]+mat[l1][l2]);
        for(int i=1;i<=top;i++) ret[stk[i]]=mx;
        return;
    }
    if(r1-l1<r2-l2) {
        int mid=(l2+r2)>>1,ltop=0,rtop=0,key=0;
        for(int i=1;i<=top;i++) {
            if(qc[stk[i]]>mid) rtop++;
            else if(qd[stk[i]]<=mid) ltop++;
            else key++;
        }
        nth_element(stk+1,stk+ltop+1,stk+top+1,[&](int x,int y) {return qd[x]<qd[y];});
        nth_element(stk+ltop+1,stk+ltop+key+1,stk+top+1,[&](int x,int y) {return qc[x]<qc[y];});
        solve(l1,r1,l2,mid,stk,ltop);
        solve(l1,r1,mid+1,r2,stk+ltop+key,rtop);
        // printf("line = %d, l1 = %d, r1 = %d, l2 = %d, r2 = %d\n",__LINE__,l1,r1,l2,r2);
        int st=ltop+1,ed=ltop+key;
        for(int i=l1;i<=r1;i++) {
            clhs(l1,i,l2,mid,1); crhs(i,r1,mid+1,r2,1);
            for(int j=st;j<=ed;j++) if(qa[stk[j]]<=i&&i<=qb[stk[j]]) {
                chkmax(ret[stk[j]],lhs[qa[stk[j]]][qc[stk[j]]][0][0]+rhs[qb[stk[j]]][qd[stk[j]]][0][0]);
                // printf("line = %d, i = %d, ret = %d\n",__LINE__,i,ret[stk[j]]);
                chkmax(ret[stk[j]],rhs[qb[stk[j]]][qd[stk[j]]][0][0]-c1[i]);
                // printf("line = %d, i = %d, ret = %d\n",__LINE__,i,ret[stk[j]]);
            }
        }
    } else {
        int mid=(l1+r1)>>1,ltop=0,rtop=0,key=0;
        for(int i=1;i<=top;i++) {
            if(qa[stk[i]]>mid) rtop++;
            else if(qb[stk[i]]<=mid) ltop++;
            else key++;
        }
        nth_element(stk+1,stk+ltop+1,stk+top+1,[&](int x,int y) {return qb[x]<qb[y];});
        nth_element(stk+ltop+1,stk+ltop+key+1,stk+top+1,[&](int x,int y) {return qa[x]<qa[y];});
        solve(l1,mid,l2,r2,stk,ltop);
        solve(mid+1,r1,l2,r2,stk+ltop+key,rtop);
        // printf("line = %d, l1 = %d, r1 = %d, l2 = %d, r2 = %d\n",__LINE__,l1,r1,l2,r2);
        int st=ltop+1,ed=ltop+key;
        for(int i=l2;i<=r2;i++) {
            clhs(l1,mid,l2,i,2); crhs(mid+1,r1,i,r2,2);
            for(int j=st;j<=ed;j++) if(qc[stk[j]]<=i&&i<=qd[stk[j]]) {
                chkmax(ret[stk[j]],lhs[qa[stk[j]]][qc[stk[j]]][0][0]+rhs[qb[stk[j]]][qd[stk[j]]][0][0]);
                chkmax(ret[stk[j]],rhs[qb[stk[j]]][qd[stk[j]]][0][0]-c2[i]);
                // printf("line = %d, i = %d, ret = %d\n",__LINE__,i,ret[stk[j]]);
            }
        }
    }
}
bool memEn;
void fl() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
int main() {
    fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
    // fl();
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=n;i++) scanf("%d",&c1[i]);
    for(int i=1;i<=n;i++) scanf("%d",&c2[i]);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mat[i][j]);
    for(int i=1;i<=Q;i++) scanf("%d%d%d%d",&qa[i],&qb[i],&qc[i],&qd[i]);
    iota(qry+1,qry+Q+1,1); solve(1,n,1,n,qry,Q);
    if(Q>1000) {
        printf("%d %d %d %d\n",qa[5],qb[5],qc[5],qd[5]);
        for(int i=1;i<=5;i++) printf("%d ",c1[i]); puts("");
        for(int i=1;i<=5;i++) printf("%d ",c2[i]); puts("");
        for(int i=1;i<=5;i++) {
            for(int j=1;j<=5;j++) {
                printf("%d ",mat[i][j]);
            }
            puts("");
        }
    }
    for(int i=1;i<=Q;i++) printf("%d\n",ret[i]);
    return 0;
}