Description

The tsundere girl Yuuka is a very cute girl. As technology advances, everyone in Gensokyo has started using mobile phones. Yuuka noticed that no one comes to her sunflower field anymore. Feeling sad, she asked around and learned that everyone dislikes the lack of Wi-Fi there, and mobile data is required to access the Internet.

What should she do? Yuuka decides to quickly deploy several Wi-Fi hotspots so that everyone can surf the Internet freely in the sunflower field.

We can approximate the sunflower field as an infinitely long rectangle with the $y$ coordinate in $[0, R]$ and the $x$ coordinate in $(-\infty, +\infty)$ (i.e., extending infinitely along the $x$-axis).

There are $n$ scenic spots inside the sunflower field that tourists often visit. Yuuka thinks that as long as these spots are covered by Wi-Fi as much as possible, the visitors will be satisfied.

Yukari Yakumo says she can help Yuuka set up Wi-Fi routers. Each standard router has a coverage radius of exactly $R$. After surveying the map, Yukari finds that outside the sunflower field there are only $m$ locations with network access, and she can only install routers there. If you install a router at point $p$, then any location $q$ with Euclidean distance between $p$ and $q$ less than or equal to $R$ will be covered by Wi-Fi.

At the same time, Yukari says that installation difficulty varies by location, so the fee also differs. Installing at the $i$-th location costs $c_i$.

Now Yuuka wants to cover as many scenic spots as possible. Under this condition, she also wants to minimize the total cost. Can you help her?

Input Format

The first line contains three integers $n, m, R$, representing the number of scenic spots, the number of network installation locations, and the width of the sunflower field.

The next $n$ lines each contain two integers $x, y$, satisfying $|x| \le 10^8, 0 \le y \le R$, describing a scenic spot. No two scenic spots share the same position.

The next $m$ lines each contain three integers $x, y, c$, satisfying $|x| \le 10^9$, $-10^8 \lt y \lt 0$ or $R \lt y \lt 10^8$, describing a network installation location and its cost. No two network installation locations share the same position.

Output Format

The first line outputs the maximum number of scenic spots that can be covered.

The second line outputs the minimum total cost under the condition that the number of covered scenic spots is maximized.

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

Hint

• For $10\%$ of the testdata, $n, m \le 20$.
• For another $30\%$ of the testdata, $n, m \le 100$, and all installation locations have $y$-coordinates greater than $R$.
• For another $60\%$ of the testdata, $n, m \le 100$.

For all testdata, $1 \le R \le 10^8$, $0 \le c \le 10^4$.

Translated by ChatGPT 5