1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <set>
#include <stdlib.h>
//---===---
#include <stdio.h>
#include <unistd.h>

char buf_in[4096000];
int buf_in_head = 0;
int buf_in_tail = 0;

static int getChar(void) {
  while (buf_in_head == buf_in_tail) {
    int rv = read(0, buf_in, sizeof(buf_in));
    if (rv > 0) {
      buf_in_head = 0;
      buf_in_tail = rv;
      break;
    };
    if (rv == 0) return EOF;
  }
  return buf_in[buf_in_head++];
}

// only 1 call is safe, and only if previously getChar() had been called.
static void ungetChar(void) {
  --buf_in_head;
}

static int getInt() {
  int dir = +1;
  int v;
  int c;
  for (;;) {
    c = getChar();
    if (c == '-') { dir *= -1; continue; };
    if (c < '0') continue;
    if (c > '9') continue;
    v = c - '0';
    break;
  };
  for (;;) {
    c = getChar();
    if (c < '0') break;
    if (c > '9') break;
    v *= 10;
    v += c - '0';
  };
  ungetChar();
  return dir * v;
}
//---===---

int n; // 1 <= n <= 200,000
int m; // 1 <= m <= 200,000
int w; // 1 <= w <= 1,000,000,000
int h; // 1 <= h <= 1,000,000,000

typedef struct {
  long long x, y;
  int v;
} tt;

tt T[200000 + 200000];

static inline int cmp(const tt * a, const tt * b) {
  if (a->x < b->x) return -1;
  if (a->x > b->x) return +1;

  if (a->y < b->y) return -1;
  if (a->y > b->y) return +1;

  if (a->v < b->v) return -1;
  if (a->v > b->v) return +1;

  return 0;
}

int void_cmp(const void * a, const void * b) {
  return cmp((const tt*)a, (const tt*)b);
}

typedef std::pair<long long,long long> p_qq;

std::set<p_qq> S;
std::set<p_qq>::iterator it;
long long sum;

int main (void) {
  int i;

  n = getInt(); // 1 <= n <= 200,000
  m = getInt(); // 1 <= m <= 200,000
  w = getInt(); // 1 <= w <= 1,000,000,000
  h = getInt(); // 1 <= h <= 1,000,000,000

  for (i = 0; i < n; ++i) {
    long long hx = h * 1LL * getInt(); // |x=getInt| <= 1,000,000,000
    long long wy = w * 1LL * getInt(); // |y=getInt| <= 1,000,000,000
    T[i].x = wy + hx; // |T[i].x| <= 2,000,000,000,000,000,000
    T[i].y = wy - hx; // |T[i].y| <= 2,000,000,000,000,000,000
    T[i].v = getInt(); // 1 <= v=getInt <= 1,000,000,000
  };

  for (i = n; i < n + m; ++i) {
    long long hx = h * 1LL * getInt(); // |x=getInt| <= 1,000,000,000
    long long wy = w * 1LL * getInt(); // |y=getInt| <= 1,000,000,000
    T[i].x = wy + hx; // |T[i].x| <= 2,000,000,000,000,000,000
    T[i].y = wy - hx; // |T[i].y| <= 2,000,000,000,000,000,000
    T[i].v = -getInt(); // 1 <= v=getInt <= 1,000,000,000
  };

  qsort(T, n + m, sizeof(tt), void_cmp);

  // S only stores positive values, 'sum' is sum of those values
  for (i = 0; i < n + m; ++i) {
    long long y = T[i].y;
    long long v = T[i].v;
    while (v) {
      it = S.lower_bound(p_qq(y, 0)); // first >=
      if ( (it != S.end()) && (it->first == y) ) {
        // perfect match - accumulate
      } else if (v > 0) {
        // non-matching positive - insert
        S.insert(p_qq(y, v));
        sum += v;
        break;
      } else if (it == S.begin()) {
        // negative and nothing before us - drop
        break;
      } else {
        // we're negative and there is something before us - accumulate into it
        --it;
        y = it->first;
      };
      // accumulate
      sum -= it->second;
      v += it->second;
      S.erase(it);
    };
  };

  printf("%lld\n", sum);

  return 0;
}