//Linkwish's code
//Ciallo～(∠・ω< )⌒★
#include<bits/stdc++.h>
#define endl '\n'
#define si static inline
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef long double ld;typedef __int128 li;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;typedef const int ci;
typedef const ll cl;const int iinf=1e9;const ll linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{

	ci N=505,M=300005;

	int n,m;
	int a[N][N],v1[N],v2[N];

	struct Que{
		int l,r,L,R,id;
		inline Que(int v,int w,int x,int y,int z){l=v,r=w,L=x,R=y,id=z;}
	};
	vector<Que> q[N<<2];
	int ans[M];
	si int ls(int x){return x<<1;}
	si int rs(int x){return x<<1|1;}
	void add(int x,int l,int r,Que k){
		if(l==r){
			ans[k.id]=-v1[l];
			for(int i=k.L;i<=k.R;i++)if(a[l][i]>v2[i])ans[k.id]+=a[l][i]-v2[i];
			gmax(ans[k.id],0);
			return ;
		}
		int mid=(l+r)>>1;
		if(k.l<=mid&&k.r>mid)return q[x].push_back(k),void();
		if(k.l<=mid)add(ls(x),l,mid,k);
		else add(rs(x),mid+1,r,k);
	}

	int f[N][N][2],g[N][N][2];
	void solve(int x,int l,int r){
		if(l==r)return ;
		int mid=(l+r)>>1;
		for(int st=1;st<=n;st++){
			for(int i=l;i<=mid+1;i++)for(int j=0;j<=n+1;j++)f[i][j][0]=f[i][j][1]=-iinf;
			for(int i=mid;i<=r;i++)for(int j=0;j<=n+1;j++)g[i][j][0]=g[i][j][1]=-iinf;

			f[mid+1][st][0]=0;
			for(int i=mid;i>=l;i--){
				f[i][st][0]=0;
				f[i][st][1]=max(f[i+1][st][1]+max(0,a[i][st]-v1[i]),a[i][st]-v1[i]-v2[st]);
				// cout<<"FS "<<i<<' '<<f[i][st][1]<<endl;
				int mx[2][2]={{0,-iinf},{f[i+1][st][1],max(-v2[st],f[i+1][st][1])+a[i][st]-v1[i]}};
				for(int j=st-1,c1,c2;j;j--){
					for(int k=0;k<2;k++){
						f[i][j][k]=f[i+1][j][k]+max(0,a[i][j]-v1[i]);
						c1=mx[k][0]+a[i][j]-v1[i]-v2[j],c2=max(mx[k][1]-v2[j],f[i+1][j][k]-v1[i])+a[i][j];
						gmax(f[i][j][k],max(c1,c2));

						gmax(mx[k][0],f[i][j][k]);
						gmax(mx[k][1],max(c1,c2));
						// cout<<"F "<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<' '<<c1<<' '<<c2<<endl;
					}
				}
			}
			for(int i=mid;i>=l;i--)
				for(int j=st;j;j--)
					for(int k=0;k<2;k++)
						gmax(f[i][j][k],f[i][j+1][k]);

			g[mid][st][0]=0;
			for(int i=mid+1;i<=r;i++){
				g[i][st][0]=0;
				g[i][st][1]=max(g[i-1][st][1]+max(0,a[i][st]-v1[i]),a[i][st]-v1[i]-v2[st]);
				// cout<<"GS "<<i<<' '<<g[i][st][1]<<endl;
				int mx[2][2]={{0,-iinf},{g[i-1][st][1],max(-v2[st],g[i-1][st][1])+a[i][st]-v1[i]}};
				for(int j=st+1,c1,c2;j<=n;j++){
					for(int k=0;k<2;k++){
						g[i][j][k]=g[i-1][j][k]+max(0,a[i][j]-v1[i]);
						c1=mx[k][0]+a[i][j]-v1[i]-v2[j],c2=max(mx[k][1]-v2[j],g[i-1][j][k]-v1[i])+a[i][j];
						gmax(g[i][j][k],max(c1,c2));

						gmax(mx[k][0],g[i][j][k]);
						gmax(mx[k][1],max(c1,c2));

						// cout<<"G "<<i<<' '<<j<<' '<<k<<' '<<g[i][j][k]<<endl;
					}
				}
			}
			for(int i=mid+1;i<=r;i++)
				for(int j=st;j<=n;j++)
					for(int k=0;k<2;k++)
						gmax(g[i][j][k],g[i][j-1][k]);

			// cout<<"ST "<<st<<endl;
			for(Que &i:q[x]){
				if(i.L<=st&&i.R>=st){
					for(int j=0;j<2;j++){
						for(int k=0;k<2;k++){
							gmax(ans[i.id],f[i.l][i.L][j]+g[i.r][i.R][k]+(j&&k)*v2[st]);
							// cout<<"GM "<<i.id<<' '<<j<<' '<<k<<' '<<f[i.l][i.L][j]<<' '<<g[i.r][i.R][k]<<' '<<(j&&k)*v2[st]<<endl;
						}
					}
				}
			}
		}

		solve(ls(x),l,mid),solve(rs(x),mid+1,r);
	}

	si void mian(){
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>v1[i];
		for(int i=1;i<=n;i++)cin>>v2[i];
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
		for(int i=1,l,r,L,R;i<=m;i++){
			cin>>l>>r>>L>>R;
			add(1,1,n,Que(l,r,L,R,i));
		}

		solve(1,1,n);

		for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
	}
}

signed main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	LinkWish::mian();
	return 0;
}