/** ____ ____ ____ __________________ ____ ____ ____ ||I || ||c || ||e || || || ||M || ||a || ||n || ||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__|| |/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\| */ #include <iostream> #include <vector> #include <algorithm> #define maxn 500005 #define PB push_back #define X first #define Y second typedef long long ll; typedef std::pair <ll, ll> pii; typedef std::pair <ll, ll> pll; typedef std::pair <ll, ll> pil; typedef std::pair <ll, ll> pli; const ll mod = 1e9 + 7; const ll INF = 1e9; int get_id(ll x , std::vector <ll> &cords) { return (int)(std::lower_bound(cords.begin() , cords.end() , x) - cords.begin()); } void read_solve() { int n , q; std::cin >> n >> q; std::vector <std::pair <ll , std::pair <pii , pii> > > v; std::vector <ll> cords = {(ll)1e12}; for(int i = 0; i < n; i++) { ll t , l , r , c; std::cin >> t >> l >> r >> c; ll x = t + llabs(r - l); pii poms = {t - l , t + l}; pii pomt = {x - r , x + r}; v.PB({c , {poms , pomt}}); cords.PB(v[i].Y.X.X); cords.PB(v[i].Y.X.Y); cords.PB(v[i].Y.Y.X); cords.PB(v[i].Y.Y.Y); } std::sort(cords.begin() , cords.end()); cords.erase(std::unique(cords.begin() , cords.end()) , cords.end()); int sz = cords.size(); std::vector <std::vector <ll> > mx(sz , std::vector <ll>(sz , 0)); std::vector <std::vector <ll> > my(sz , std::vector <ll>(sz , 0)); std::vector <std::vector <ll> > dp(sz , std::vector <ll>(sz , 0)); for(int i = 0; i < n; i++) { int au = get_id(v[i].Y.X.X , cords); int av = get_id(v[i].Y.X.Y , cords); int bu = get_id(v[i].Y.Y.X , cords); int bv = get_id(v[i].Y.Y.Y , cords); if(v[i].Y.X.X == v[i].Y.Y.X) for(int j = av; j < bv; j++) my[au][j] = v[i].X; else for(int j = au; j < bu; j++) mx[j][av] = v[i].X; } for(int i = sz - 1; i >= 0; i--) for(int j = sz - 1; j >= 0; j--) { if(i + 1 < sz) dp[i][j] = std::max(dp[i][j] , dp[i + 1][j] + (ll)(cords[i + 1] - cords[i]) * mx[i][j]); if(j + 1 < sz) dp[i][j] = std::max(dp[i][j] , dp[i][j + 1] + (ll)(cords[j + 1] - cords[j]) * my[i][j]); } while(q--) { ll pp , dx; std::cin >> pp >> dx; int idu = get_id(pp - dx , cords); int idv = get_id(pp + dx , cords); ll ans = dp[idu][idv]; if(idu > 0) for(int i = idv; i < sz; i++) ans = std::max(ans , dp[idu][i] + (ll)(cords[idu] - pp + dx) * mx[idu - 1][i]); if(idv > 0) for(int i = idu; i < sz; i++) ans = std::max(ans , dp[i][idv] + (ll)(cords[idv] - pp - dx) * my[i][idv - 1]); std::cout << ans / 2 << "\n"; } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); ll tests = 1; //std::cin >> tests; while(tests--) { read_solve(); } return 0; }