No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

傲娇少女幽香是一个很萌很萌的妹子。随着科技的进步，幻想乡的大家也开始使用手机了。这时幽香发现没人来她的太阳花田玩了，她感到很伤心，于是向别人打听了一下，才知道原来大家都嫌弃这里没有 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$，表示一个网络架设点的位置和花费。两个网络架设点不会重合。

输出格式

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

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

样例 #1

样例输入 #1

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

样例输出 #1

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$。