#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class MagicGirl { public: void solve(void) { int N,K; cin>>N>>K; // いもす法 // 要は遅延評価。最後に全平面をスキャンするときに // 評価されるように区間情報を更新しておく int offset = 2; // 境界処理用 int W,H,ox,oy; // monster の存在範囲をフィールドサイズとかんがえてよい W = H = 1000 + offset; ox = W/2; oy = H/2; vector> monster; REP(i, N) { int x,y,hp; cin>>x>>y>>hp; // 座標を (0,0)-(W-1,H-1) 以内に変換 x += ox; y += oy; monster.emplace_back(x,y,hp); } // いもす法。ダメージ計算の参照点を更新しておく // 参照点は範囲の左下と右上+(1,1) // メモリは左上分 +1 ひろげて確保しておく vector> damage(H+1, vector(W+1, 0)); REP(i,K) { int x,y,w,h,d; cin>>x>>y>>w>>h>>d; x += ox; y += oy; // -5 5 0 // ...*.....* ..05555555 // ://///: 05555555 // ://///: => 05555555 // ...5.....*-5 ..05555555 // : : 00000000 // damage[min(y+h+1,H)][min(x+w+1,W)] += d; damage[min(y+h+1,H)][x] -= d; damage[y][min(x+w+1,W)] -= d; damage[y][x] += d; } vector> sum(H+1, vector(W+1, 0)); // O(W*H) FOR(y,1,H+1) FOR(x,1,W+1) sum[y][x] += sum[y][x-1] + sum[y-1][x] - sum[y-1][x-1] + damage[y][x]; int ans = 0; for (auto m : monster) { int x,y,hp; tie(x,y,hp) = m; ans += max(0,hp - sum[y][x]); } cout<solve(); delete obj; return 0; } #endif