#include<bits/stdc++.h>

#define i128 __int128
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define tup tuple<int, int, int>
#define mkt make_tuple
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

#define int long long

using namespace std;

mt19937 gen(time(0));

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}
inline void write(int x) { if(x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void writee(int x) { write(x); putchar(10); }

const int N = 6005, M = 3e6 + 5;

int n, m, tot, val[N], r[N][N], c[N][N];
int lx, ly, X[N], Y[N];
int ans[M], f[N][N];
pii s[N], t[N]; 
vc<tup> q[N][N];

inline void trans(pii &u) { auto [x, y] = u; u.first = x + y; u.second = y - x; }
inline int findx(int x) { return lower_bound(X + 1, X + 1 + lx, x) - X; }
inline int findy(int y) { return lower_bound(Y + 1, Y + 1 + ly, y) - Y; }

inline void init_grid() {
	for(int i = 1, t, a, b; i <= n; i++) {
		t = read(); a = read(); b = read(); val[i] = read() / 2;
		s[i] = mkp(a, t); ::t[i] = mkp(b, t + abs(a - b));
		trans(s[i]); trans(::t[i]);
		X[++lx] = s[i].first; Y[++ly] = s[i].second;
		X[++lx] = ::t[i].first; Y[++ly] = ::t[i].second;
	}
	sort(X + 1, X + 1 + lx); lx = unique(X + 1, X + 1 + lx) - X - 1;
	sort(Y + 1, Y + 1 + ly); ly = unique(Y + 1, Y + 1 + ly) - Y - 1;
	rep(i, 1, n) {
		auto &[sx, sy] = s[i];
		auto &[tx, ty] = t[i];
		sx = findx(sx); sy = findy(sy);
		tx = findx(tx); ty = findy(ty);
		if(sx == tx) { rep(j, sy, ty - 1) c[sx][j] = max(c[sx][j], val[i]); }
		else         { rep(j, sx, tx - 1) r[j][sy] = max(r[j][sy], val[i]); }
	}
}

inline void init_query() {
	for(int i = 1, t, u, x, y; i <= m; i++) {
		t = read(); u = read(); 
		x = findx(u + t); y = findy(t - u);
		if(x > lx || y > ly) continue;
		q[x][y].pb(mkt(i, X[x] - (u + t), Y[y] - (t - u)));
	}
}

inline void init_f() {
	lep(j, ly, 1) lep(i, lx, 1) 
		f[i][j] = max(f[i + 1][j] + (X[i + 1] - X[i]) * r[i][j], f[i][j + 1] + (Y[j + 1] - Y[j]) * c[i][j]);
}

struct convex {
	vc<pii> a; int tl;
	convex() { a.clear(); tl = 0; }
	inline void push(pii u) {
		while(tl && a[tl - 1].first <= u.first) --tl, a.pop_back();
		while(tl > 1 && (i128)(u.second - a[tl - 1].second) * (a[tl - 2].first - a[tl - 1].first) 
		              > (i128)(a[tl - 1].second - a[tl - 2].second) * (a[tl - 1].first - u.first)) a.pop_back(), --tl;
		a.pb(u); ++tl;
	}
	inline int ask(int k) {
		if(!tl) return 0;
		int l = 1, r = tl - 1, mid;
		while(l <= r) {
			mid = l + r >> 1;
			if((i128)(a[mid].second - a[mid - 1].second) <= (i128)k * (a[mid - 1].first - a[mid].first)) r = mid - 1;
			else l = mid + 1;
		}
		return k * a[r].first + a[r].second;
	}
} Q[N];

inline void solve() {
	lep(j, ly, 1) {
		convex row; 
		lep(i, lx, 1) {
			row.push(mkp(c[i][j - 1], f[i][j]));
			Q[i].push(mkp(r[i - 1][j], f[i][j]));
			for(auto [id, u, v] : q[i][j]) {
				ans[id] = max(ans[id], Q[i].ask(u));
				ans[id] = max(ans[id], row.ask(v));
			}
		}
	}
}

signed main() {
	n = read(); m = read();
	
	init_grid();
	init_f();
	init_query();	
	
	solve();
	
	rep(i, 1, m) writee(ans[i]);
	
	return 0;
}