bzoj#P4251. [PA2014]Muzeum

[PA2014]Muzeum

题目描述

吉丽的漫展有 nn 件手办和 mm 名警卫。

现在我们对其建立平面直角坐标系,每个手办和警卫都可以看做一个点。警卫们的目光都朝着 yy 轴负方向,且都有相同大小的视角。警卫可以看见自己视角内(包括边界上的点)的所有手办,不用考虑视线的遮挡。

你打算抢劫吉丽的漫展,但不想被警卫发现。为了实施这次抢劫计划,你可以事先贿赂某些警卫,让他们闭上眼睛。只要某件手办不在任何睁着眼睛的警卫的视野内,你就可以偷走它。你知道每件手办的价格,以及每位警卫需要接受多少钱的贿赂。你想知道自己的最大收益是多少。

输入格式

第一行两个整数 n,mn,m,分别表示手办的数量和警卫的数量。

第二行两个整数 w,hw,h,表示每个警卫的视角的一半的正切值是 wh\dfrac{w}{h}

接下来 nn 行,每行三个整数 xi,yi,vix_i,y_i,v_i,表示手办的坐标为 (xi,yi)(x_i, y_i),价格为 viv_i

接下来 mm 行,格式同上,表示警卫的坐标为 (xi,yi)(x_i,y_i),需接受贿赂的金额为 viv_i

保证每个点最多只有一个手办或一个警卫

输出格式

输出仅一行表示最大收益。

输入样例

5 3
2 3
2 6 2
5 1 3
5 5 8
7 3 4
8 6 1
3 8 3
4 3 5
5 7 6

输出样例

6

样例解释

贿赂售价为 3+6=93+6=9 元的两个警卫,偷走价值共 2+8+4+1=152+8+4+1=15 元的 4444 个手办,收益 159=615-9=6 元。

数据规模与约定

对于 100%100\% 的数据,1n,m2×1051\le n,m\le 2\times 10^51w,h1091 \le w,h \le 10^9109xi,yi109-10^9 \le x_i,y_i \le 10 ^ 91vi1091 \le v_i \le 10 ^ 9