#2139. 「ZJOI2015」幻想乡 Wi-Fi 搭建计划

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

傲娇少女幽香是一个很萌很萌的妹子。随着科技的进步,幻想乡的大家也开始使用手机了。这时幽香发现没人来她的太阳花田玩了,她感到很伤心,于是向别人打听了一下,才知道原来大家都嫌弃这里没有 Wi-Fi,手机上网还需要流量。

怎么办呢?幽香决定赶快搭建几个 Wi-Fi 点,让所有人都能在太阳花田里畅快地上网。

我们可以近似地把太阳花田看成一个 y 轴在 [0,R] 之间, x 坐标在 (-\infty,+\infty) (也就是在 x 轴上无限延伸)的无限长方形。

太阳花田里面有 n 个景点,是游客们经常光顾的,幽香认为只要让这些景点尽量被 Wi-Fi 覆盖,那么游客们就肯定心满意足了。

八云紫表示她可以帮幽香架设 Wi-Fi 路由器。现在通用的路由器,每个的覆盖半径正好也是 R 。八云紫扫视了一遍地图,发现在太阳花田外面,只有 m 个有网络的地点,她只可以在那里架设路由器。如果你在点 p 搭建了路由器,那么位于 q 的地点,只要 p q 的欧几里得距离小于等于 R q 点就会被 Wi-Fi 覆盖。

同时八云紫表示,架设难度随着地点的不同而不同,所以收费也不一样,在第 i 个位置架设需要 c_i 的钱。

现在幽香想要覆盖尽量多的景点,在这个前提下,幽香也想要尽量节省钱。你能帮助她吗?

输入格式

输入第一行三个整数 n,m,R ,分别表示景点的数量,网络架设地点的数量和太阳花田的宽度。

接下来 n 行,每行两个整数 x,y ,满足 |x|\le 10^8,0\le y\le R ,表示一个景点。两个景点的位置不会重合。

接下来 m 行,每行三个整数 x,y,c ,满足 |x|\le 10^9 -10^8\lt y\lt 0 或者 R\lt y\lt 10^8 ,表示一个网络假设点的位置和花费。两个网络架设点不会重合。

输出格式

输出第一行表示最多覆盖的景点数。

第二行表示在覆盖景点数最多的前提下,最少的花费。

样例

样例输入

10 10 10000
6743 2963
3505 1986
3565 7235
1735 5522
16877 5597
11621 6
3100 8243
1750 6173
5709 7671
7915 3915
14339 -438 3075
4278 15210 8371
13996 19000 6750
17049 -4969 7788
737 16339 2934
904 14023 2322
8982 14759 4311
13102 11458 5554
4135 12183 576
5087 -2459 6787

样例输出

10
10438

数据范围与提示

对于 10\% 的数据, n,m\le 20

对于另 30\% 的数据, n,m\le 100 ,所有网络架设点的 y 坐标都大于 R

对于另 60\% 的数据, n,m\le 100

对于全部数据, 1\le R\le 10^8,0\le c\le 10^4