#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2805;
const int MAXV = 5605;
const int MAXQ = 3e6 + 5;
const int INF = 1e18;
void chmax(int&x, int val)
{
x = max(x, val);
}
int n,q;
int t[MAXN], a[MAXN], b[MAXN], c[MAXN];
pair<int,int> from[MAXN], to[MAXN];
map<int,int> mp1, mp2;
unordered_map<int,int> nrm1, nrm2;
int cate1, cate2;
int inv1[MAXV], inv2[MAXV];
int dp[MAXV][MAXV];
int move1[MAXV][MAXV], move2[MAXV][MAXV];
vector<int> baga[MAXV], scoate[MAXV];
void precalc()
{
for(int d1=1;d1<=cate1;d1++)
{
for(int i=1;i<=n;i++)
{
if(from[i].first == to[i].first && nrm1[from[i].first] == d1)
{
baga[nrm2[from[i].second]].push_back(c[i]);
scoate[nrm2[to[i].second]].push_back(c[i]);
}
}
multiset<int> s;
for(int j=1;j<=cate2;j++)
{
for(int x:baga[j])
s.insert(x);
for(int x:scoate[j])
s.erase(s.find(x));
baga[j].clear();
scoate[j].clear();
if(!s.empty())
move2[d1][j] = (*s.rbegin());
}
}
for(int d2=1;d2<=cate2;d2++)
{
for(int i=1;i<=n;i++)
{
if(from[i].second == to[i].second && nrm2[from[i].second] == d2)
{
baga[nrm1[from[i].first]].push_back(c[i]);
scoate[nrm1[to[i].first]].push_back(c[i]);
}
}
multiset<int> s;
for(int j=1;j<=cate1;j++)
{
for(int x:baga[j])
s.insert(x);
for(int x:scoate[j])
s.erase(s.find(x));
baga[j].clear();
scoate[j].clear();
if(!s.empty())
move1[j][d2] = (*s.rbegin());
}
}
for(int i=cate1;i>=1;i--)
{
for(int j=cate2;j>=1;j--)
{
chmax(dp[i][j], dp[i + 1][j] + move1[i][j] * (inv1[i + 1] - inv1[i]));
chmax(dp[i][j], dp[i][j + 1] + move2[i][j] * (inv2[j + 1] - inv2[j]));
}
}
}
int qpoz[MAXQ], qt[MAXQ], rez[MAXQ];
pair<int,int> init[MAXQ];
pair<int,int> ds[MAXQ];
struct line
{
int m, b;
int eval(int x) { return m * x + b; }
};
namespace CONVEX_HULL
{
vector<line> lichao;
vector<int> used;
void first_init()
{
used.clear();
}
void fake_upd(int x)
{
used.push_back(x);
}
void true_init()
{
sort(used.begin(), used.end());
used.erase(unique(used.begin(), used.end()), used.end());
lichao.clear();
lichao.resize(4 * used.size() + 2);
}
void upd(int nod, int st, int dr, line newv)
{
int mij = (st + dr) / 2;
if(newv.eval(used[mij]) > lichao[nod].eval(used[mij]))
swap(newv, lichao[nod]);
if(st == dr)
return;
if(newv.eval(used[st]) > lichao[nod].eval(used[st]))
upd(nod*2, st, mij, newv);
else if(newv.eval(used[dr]) > lichao[nod].eval(used[dr]))
upd(nod*2+1, mij+1, dr, newv);
}
void add(line a)
{
upd(1, 0, (int)used.size() - 1, a);
}
int qry(int nod, int st, int dr, int x)
{
int mxm = lichao[nod].eval(x);
if(st < dr)
{
int mij = (st + dr) / 2;
if(x <= used[mij])
mxm = max(mxm, qry(nod*2, st, mij, x));
else
mxm = max(mxm, qry(nod*2+1, mij+1, dr, x));
}
return mxm;
}
int query(int x)
{
return qry(1, 0, (int)used.size() - 1, x);
}
}
vector<int> ofx[MAXV];
void solve_queries()
{
for(int i=1;i<=q;i++)
{
int d1 = lower_bound(inv1 + 1, inv1 + 1 + cate1, init[i].first) - inv1;
int d2 = lower_bound(inv2 + 1, inv2 + 1 + cate2, init[i].second) - inv2;
ds[i] = {d1, d2};
if(d1 == cate1 + 1 || d2 == cate2 + 1)
{
ds[i] = {-1, -1};
continue;
}
assert(inv1[d1] >= init[i].first);
assert(inv2[d2] >= init[i].second);
//for(int x=d1;x<=cate1;x++)
// rez[i] = max(rez[i], (dp[x][d2] + move2[x][d2 - 1] * inv2[d2]) - move2[x][d2 - 1] * init[i].second);
//for(int x=d2;x<=cate2;x++)
// rez[i] = max(rez[i], dp[d1][x] + move1[d1 - 1][x] * inv1[d1] - move1[d1 - 1][x] * init[i].first);
}
for(int d2=1;d2<=cate2;d2++)
{
for(int x=1;x<=cate1;x++)
ofx[x].clear();
CONVEX_HULL::first_init();
for(int i=1;i<=q;i++)
if(ds[i].second == d2)
{
ofx[ds[i].first].push_back(i);
CONVEX_HULL::fake_upd(init[i].second);
}
CONVEX_HULL::true_init();
for(int x=cate1;x>=1;x--)
{
line cur;
cur.b = dp[x][d2] + move2[x][d2 - 1] * inv2[d2];
cur.m = -move2[x][d2 - 1];
CONVEX_HULL::add(cur);
for(int i:ofx[x])
rez[i] = max(rez[i], CONVEX_HULL::query(init[i].second));
}
}
for(int d1=1;d1<=cate1;d1++)
{
for(int x=1;x<=cate2;x++)
ofx[x].clear();
CONVEX_HULL::first_init();
for(int i=1;i<=q;i++)
if(ds[i].first == d1)
{
ofx[ds[i].second].push_back(i);
CONVEX_HULL::fake_upd(init[i].first);
}
CONVEX_HULL::true_init();
for(int x=cate2;x>=1;x--)
{
line cur;
cur.b = dp[d1][x] + move1[d1 - 1][x] * inv1[d1];
cur.m = -move1[d1 - 1][x];
CONVEX_HULL::add(cur);
for(int i:ofx[x])
rez[i] = max(rez[i], CONVEX_HULL::query(init[i].first));
}
}
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>t[i]>>a[i]>>b[i]>>c[i];
c[i] /= 2;
from[i] = {t[i] - a[i], t[i] + a[i]};
int end_t = t[i] + abs(a[i] - b[i]);
to[i] = {end_t - b[i], end_t + b[i]};
mp1[from[i].first]++;
mp2[from[i].second]++;
mp1[to[i].first]++;
mp2[to[i].second]++;
}
for(int i=1;i<=q;i++)
{
cin>>qt[i]>>qpoz[i];
init[i] = {qt[i] - qpoz[i], qt[i] + qpoz[i]};
}
for(auto it:mp1)
{
nrm1[it.first] = ++cate1;
inv1[cate1] = it.first;
}
for(auto it:mp2)
{
nrm2[it.first] = ++cate2;
inv2[cate2] = it.first;
}
assert(cate1 < MAXV);
assert(cate2 < MAXV);
precalc();
solve_queries();
for(int i=1;i<=q;i++)
cout<<rez[i]<<"\n";
return 0;
}
