#pragma GCC optimize ("Ofast") #include using namespace std; template struct cLtraits_identity{ using type = T; } ; template using cLtraits_try_make_signed = typename conditional< is_integral::value, make_signed, cLtraits_identity >::type; template struct cLtraits_common_type{ using tS = typename cLtraits_try_make_signed::type; using tT = typename cLtraits_try_make_signed::type; using type = typename common_type::type; } ; void*wmem; char memarr[96000000]; template inline auto min_L(S a, T b) -> typename cLtraits_common_type::type{ return (typename cLtraits_common_type::type) a <= (typename cLtraits_common_type::type) b ? a : b; } template inline auto max_L(S a, T b) -> typename cLtraits_common_type::type{ return (typename cLtraits_common_type::type) a >= (typename cLtraits_common_type::type) b ? a : b; } template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){ walloc1d(arr, x2-x1, mem); (*arr) -= x1; } template void malloc2d(T ***arr, int x, int y){ int i; (*arr) = (T**)malloc(x*sizeof(T*)); (*arr)[0] = (T*)malloc(x*y*sizeof(T)); int Q5rsz4fz = x; for(i=(1);i<(Q5rsz4fz);i++){ (*arr)[i]=(*arr)[i-1]+y; } } template void free2d(T **arr){ free(arr[0]); free(arr); } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } template struct DijkstraHeap{ int*hp; int*place; int size; char*visited; T*val; void malloc(int N){ hp = (int*)std::malloc(N*sizeof(int)); place = (int*)std::malloc(N*sizeof(int)); visited = (char*)std::malloc(N*sizeof(char)); val = (T*)std::malloc(N*sizeof(T)); } void free(){ std::free(hp); std::free(place); std::free(visited); std::free(val); } void walloc(int N, void **mem=&wmem){ walloc1d(&hp, N, mem); walloc1d(&place, N, mem); walloc1d(&visited, N, mem); walloc1d(&val, N, mem); } void init(int N){ int i; size = 0; for(i=(0);i<(N);i++){ place[i]=-1; } for(i=(0);i<(N);i++){ visited[i]=0; } } void up(int n){ int m; while(n){ m=(n-1)/2; if(val[hp[m]]<=val[hp[n]]){ break; } swap(hp[m],hp[n]); swap(place[hp[m]],place[hp[n]]); n=m; } } void down(int n){ int m; for(;;){ m=2*n+1; if(m>=size){ break; } if(m+1val[hp[m+1]]){ m++; } if(val[hp[m]]>=val[hp[n]]){ break; } swap(hp[m],hp[n]); swap(place[hp[m]],place[hp[n]]); n=m; } } void change(int n, T v){ if(visited[n]||(place[n]>=0&&val[n]<=v)){ return; } val[n]=v; if(place[n]==-1){ place[n]=size; hp[size++]=n; up(place[n]); } else{ up(place[n]); } } int pop(void){ int res=hp[0]; place[res]=-1; size--; if(size){ hp[0]=hp[size]; place[hp[0]]=0; down(0); } visited[res]=1; return res; } } ; template struct Grid2d{ int r; int c; T**d; int set_s; int set_d; T**d_s; int**up; int**dw; int**lf; int**rg; void malloc(const int rr, const int cc){ r = rr; c = cc; set_s = 0; set_d = 0; malloc2d(&d, r, c); } void free(void){ free2d(d); if(set_s){ free2d(d_s); } if(set_d){ free2d(up); free2d(dw); free2d(lf); free2d(rg); } } T*operator[](int a){ return d[a]; } void setSum(void){ int i; int j; if(set_s == 0){ set_s = 1; malloc2d(&d_s, r+1, c+1); } for(i=(0);i<(r+1);i++){ d_s[i][0] = 0; } for(j=(0);j<(c+1);j++){ d_s[0][j] = 0; } for(i=(0);i<(r);i++){ for(j=(0);j<(c);j++){ d_s[i+1][j+1] = d_s[i][j+1] + d_s[i+1][j] - d_s[i][j] + d[i][j]; } } } void setDir(void){ int i; int j; if(set_d == 0){ set_d = 1; malloc2d(&up, r, c); malloc2d(&dw, r, c); malloc2d(&lf, r, c); malloc2d(&rg, r, c); } for(j=(0);j<(c);j++){ up[0][j] = 1; } for(i=(1);i<(r);i++){ for(j=(0);j<(c);j++){ if(d[i][j]==d[i-1][j]){ up[i][j] = 1 + up[i-1][j]; } else{ up[i][j] = 1 ; } } } for(j=(0);j<(c);j++){ dw[r-1][j] = 1; } for(i=r-2;i>=0;i--){ for(j=(0);j<(c);j++){ if(d[i][j]==d[i+1][j]){ dw[i][j] = 1 + dw[i+1][j]; } else{ dw[i][j] = 1 ; } } } for(i=(0);i<(r);i++){ lf[i][0] = 1; for(j=(1);j<(c);j++){ if(d[i][j]==d[i][j-1]){ lf[i][j] = 1 + lf[i][j-1]; } else{ lf[i][j] = 1 ; } } } for(i=(0);i<(r);i++){ rg[i][c-1] = 1; for(j=c-2;j>=0;j--){ if(d[i][j]==d[i][j+1]){ rg[i][j] = 1 + rg[i][j+1]; } else{ rg[i][j] = 1 ; } } } } void setDirMatch(const T v){ int i; int j; if(set_d == 0){ set_d = 1; malloc2d(&up, r, c); malloc2d(&dw, r, c); malloc2d(&lf, r, c); malloc2d(&rg, r, c); } for(j=(0);j<(c);j++){ if(d[0][j]==v){ up[0][j] =1; } else{ up[0][j] =0; } } for(i=(1);i<(r);i++){ for(j=(0);j<(c);j++){ if(d[i][j]==v){ up[i][j] =1 + up[i-1][j]; } else{ up[i][j] =0; } } } for(j=(0);j<(c);j++){ if(d[r-1][j]==v){ dw[r-1][j] =1; } else{ dw[r-1][j] =0; } } for(i=r-2;i>=0;i--){ for(j=(0);j<(c);j++){ if(d[i][j]==v){ dw[i][j] =1 + dw[i+1][j]; } else{ dw[i][j] =0; } } } for(i=(0);i<(r);i++){ if(d[i][0]==v){ lf[i][0] =1; } else{ lf[i][0] =0; } for(j=(1);j<(c);j++){ if(d[i][j]==v){ lf[i][j] =1 + lf[i][j-1]; } else{ lf[i][j] =0; } } } for(i=(0);i<(r);i++){ if(d[i][c-1]==v){ rg[i][c-1] =1; } else{ rg[i][c-1] =0; } for(j=c-2;j>=0;j--){ if(d[i][j]==v){ rg[i][j] =1 + rg[i][j+1]; } else{ rg[i][j] =0; } } } } inline T getSum(const int r1, const int c1, const int r2, const int c2){ return d_s[r2+1][c2+1] - d_s[r1][c2+1] - d_s[r2+1][c1] + d_s[r1][c1]; } template inline void getDist4(int sr, int sc, S **res, void *mem = wmem){ int i; int j; int k; DijkstraHeap hp; hp.walloc(r*c); hp.init(r*c); if(d[sr][sc] >= 0){ hp.change(sr*c+sc, d[sr][sc]); } while(hp.size){ k = hp.pop(); i = k / c; j = k % c; if(i-1 >= 0 && d[i-1][j] >= 0){ hp.change((i-1)*c+j, hp.val[k]+d[i-1][j]); } if(i+1 < r && d[i+1][j] >= 0){ hp.change((i+1)*c+j, hp.val[k]+d[i+1][j]); } if(j-1 >= 0 && d[i][j-1] >= 0){ hp.change(i*c+(j-1), hp.val[k]+d[i][j-1]); } if(j+1 < c && d[i][j+1] >= 0){ hp.change(i*c+(j+1), hp.val[k]+d[i][j+1]); } } for(i=(0);i<(r);i++){ for(j=(0);j<(c);j++){ if(hp.visited[i*c+j]){ res[i][j] =hp.val[i*c+j]; } else{ res[i][j] =-1; } } } } template inline void getDist4_BFS(int sr, int sc, S **res, void *mem = wmem){ int i; int j; int k; int*q; int qs=0; int qe=0; walloc1d(&q,r*c,&mem); for(i=(0);i<(r);i++){ for(j=(0);j<(c);j++){ res[i][j] = -1; } } if(d[sr][sc] >= 0){ res[sr][sc] = 1; } q[qe++] = sr*c+sc; while(qs < qe){ k = q[qs++]; i = k / c; j = k % c; if(i-1 >= 0 && d[i-1][j] >= 0 && res[i-1][j]==-1){ res[i-1][j] = res[i][j] + 1; q[qe++] = (i-1)*c + j; } if(i+1 < r && d[i+1][j] >= 0 && res[i+1][j]==-1){ res[i+1][j] = res[i][j] + 1; q[qe++] = (i+1)*c + j; } if(j-1 >= 0 && d[i][j-1] >= 0 && res[i][j-1]==-1){ res[i][j-1] = res[i][j] + 1; q[qe++] = i*c + (j-1); } if(j+1 < c && d[i][j+1] >= 0 && res[i][j+1]==-1){ res[i][j+1] = res[i][j] + 1; q[qe++] = i*c + (j+1); } } } } ; int H; int W; int N; int M; int T[100000]; int U[100000]; int L[100000]; int R[100000]; int A[100000]; int X[100000]; int Y[100000]; int B[100000]; int C[100000]; Grid2d a; int main(){ int i; wmem = memarr; int x1; int x2; int y1; int y2; int res = 0; rd(H); rd(W); rd(N); rd(M); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){ rd(T[Lj4PdHRW]);T[Lj4PdHRW] += (-1); rd(U[Lj4PdHRW]);U[Lj4PdHRW] += (-1); rd(L[Lj4PdHRW]);L[Lj4PdHRW] += (-1); rd(R[Lj4PdHRW]);R[Lj4PdHRW] += (-1); rd(A[Lj4PdHRW]); } } { int e98WHCEY; for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){ rd(X[e98WHCEY]);X[e98WHCEY] += (-1); rd(Y[e98WHCEY]);Y[e98WHCEY] += (-1); rd(B[e98WHCEY]); rd(C[e98WHCEY]); } } a.malloc(H+1,W+1); for(i=(0);i<(H+1);i++){ int j; for(j=(0);j<(W+1);j++){ a[i][j] = 0; } } for(i=(0);i<(M);i++){ x1 =max_L(0, X[i] - B[i]); x2 =min_L(H, X[i] + B[i]); y1 =max_L(0, Y[i] - B[i]); y2 =min_L(W, Y[i] + B[i]); a[x2][y2] += C[i]; if(x1 > 0){ a[x1-1][y2] -= C[i]; } if(y1 > 0){ a[x2][y1-1] -= C[i]; } if(x1 > 0 && y1 > 0){ a[x1-1][y1-1] += C[i]; } } for(i=(H+1)-1;i>=(0);i--){ int j; for(j=(W+1)-1;j>=(1);j--){ a[i][j-1] += a[i][j]; } } for(i=(H+1)-1;i>=(1);i--){ int j; for(j=(W+1)-1;j>=(0);j--){ a[i-1][j] += a[i][j]; } } a.setSum(); for(i=(0);i<(N);i++){ if(a.getSum(T[i],L[i],U[i],R[i]) < A[i]){ res++; } } wt_L(res); wt_L('\n'); return 0; } // cLay version 20210405-1 // --- original code --- // int H, W, N, M; // int T[1d5], U[], L[], R[], A[]; // int X[], Y[], B[], C[]; // Grid2d a; // { // int x1, x2, y1, y2, res = 0; // rd(H,W,N,M,(T--,U--,L--,R--,A)(N),(X--,Y--,B,C)(M)); // a.malloc(H+1,W+1); // rep(i,H+1) rep(j,W+1) a[i][j] = 0; // rep(i,M){ // x1 = max(0, X[i] - B[i]); // x2 = min(H, X[i] + B[i]); // y1 = max(0, Y[i] - B[i]); // y2 = min(W, Y[i] + B[i]); // a[x2][y2] += C[i]; // if(x1 > 0) a[x1-1][y2] -= C[i]; // if(y1 > 0) a[x2][y1-1] -= C[i]; // if(x1 > 0 && y1 > 0) a[x1-1][y1-1] += C[i]; // } // rrep(i,H+1) rrep(j,1,W+1) a[i][j-1] += a[i][j]; // rrep(i,1,H+1) rrep(j,W+1) a[i-1][j] += a[i][j]; // // wt(a(H+1,W+1)); // a.setSum(); // rep(i,N){ // if(a.getSum(T[i],L[i],U[i],R[i]) < A[i]) res++; // } // wt(res); // }