P5996 [PA 2014] Muzeum

题目描述

吉丽的漫展有 $n$ 件手办和 $m$ 名警卫。 现在我们对其建立平面直角坐标系,每个手办和警卫都可以看做一个点。警卫们的目光都朝着 $y$ 轴负方向,且都有相同大小的视角。警卫可以看见自己视角内(包括边界上的点)的所有手办,不用考虑视线的遮挡。 你打算抢劫吉丽的漫展,但不想被警卫发现。为了实施这次抢劫计划,你可以事先贿赂某些警卫,让他们闭上眼睛。只要某件手办不在任何睁着眼睛的警卫的视野内,你就可以偷走它。你知道每件手办的价格,以及每位警卫需要接受多少钱的贿赂。你想知道自己的最大收益是多少。

输入格式

输出格式

说明/提示

对于 $100\%$ 的数据,$1\le n,m\le 2\times 10^5$,$1\le w,h\le 10^9$,$-10^9\le x_i,y_i\le 10^9$,$1\le v_i\le 10^9$。 ---- ### 样例解释: ![](https://cdn.luogu.com.cn/upload/image_hosting/zxt0if8b.png) 贿赂 售价为 $3+6=9$ 元的两个警卫,偷走 价值共$2+8+4+1=15$ 元的 $4$ 个手办,收益 $15-9=6$ 元。