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
#include <cstdio>
#include <algorithm>
#include <stack>

int w,h;
int n,m; 
struct point_t {
	int x, y;
	int value;
	void scan() {
		scanf("%d %d %d", &x, &y, &value);
	}
	bool operator<(const point_t &o) const {
		return 1LL*h*(o.x-x) > 1LL*w*(y-o.y);
	}
	point_t operator-() const {
		point_t x = *this;
		x.value = -x.value;
		return x;
	}
};

point_t all[400000];
point_t guards[200000];
long long sumtree[200000];

bool compByY(const point_t &a, const point_t &b) {
	long long A = 1LL*h*(b.x-a.x), B = 1LL*w*(b.y-a.y);
	if( A == B )
		return b < a;
	return A > B;
}

void sumtree_set(point_t x, int value) {
	int l = 0, r = m;
	while( l < r ) {
		int mid = (l+r)/2;
		if( guards[mid] < x )
			l = mid+1;
		else {
			sumtree[mid] += value;
			r = mid;
		}
	}
}
long long sumtree_get(point_t x) {
	int l = 0, r = m;
	long long value = 0;
	while( l < r ) {
		int mid = (l+r)/2;
		if( x < guards[mid] )
			r = mid;
		else {
			value += sumtree[mid];
			l = mid+1;
		}
	}
	return value;
}

void append_stack(std::stack<std::pair<long long, point_t> >& stack, long long &profit) {
	while( not stack.empty() and stack.top().first < 0 )
		stack.pop();
	while( not stack.empty() ) {
		//printf("buying (%d, %d). cost = %d, profit = %lld\n", stack.top().second.x, stack.top().second.y, -stack.top().second.value, stack.top().first );
		profit += stack.top().first;
		stack.pop();
	}
	//puts("---");
}

int main() {
	scanf("%d %d %d %d", &n, &m, &w, &h );

	long long profit = 0;
	for( int i = 0; i < n; i++ ) {
		all[i].scan();
		profit += all[i].value;
	}

	for( int i = 0;	i < m; i++ ) {
		guards[i].scan();
		all[n+i] = -guards[i];
	}

	std::sort(guards, guards+m);

	for( int i = 0; i < n; i++ )
		sumtree_set(all[i], all[i].value);

	std::sort(all, all+n+m, compByY);

	profit -= sumtree_get(guards[m-1]);

	std::stack<std::pair<long long, point_t> > stack;
	for( int i = 0; i < n+m; i++ ) {
		if( all[i].value > 0 ) {
			sumtree_set(all[i], -all[i].value);
			continue;
		}
		long long value = sumtree_get(all[i]);

		if( stack.empty() ) {
			stack.push( std::make_pair( value+all[i].value, all[i] ) );
			continue;
		}
		if( all[i] < stack.top().second ) {
			if( value+all[i].value < 0 )
				stack.top().first -= value;
			else
				stack.top().first += all[i].value;
		} else {
			stack.top().first -= sumtree_get(stack.top().second);
			stack.push( std::make_pair( value+all[i].value, all[i] ) );
		}
		
		if( stack.top().first < 0 ) 
			append_stack( stack, profit );
	}
	append_stack( stack, profit );

	printf("%lld\n", profit );
}