P3344 [ZJOI2015] Gensokyo Wi-Fi Deployment Plan

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?

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.

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.

- 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