Background

JYY has recently become addicted to a tower defense game. In the game, besides building structures, JYY can also use bombs to deal area damage to enemies on the screen.

Problem Description

The game map can be simply regarded as a two-dimensional plane. JYY has built $N$ buildings, and each building is a circle. The center of the $i$-th building is at $(x_i, y_i)$ and its radius is $r_i$. There are $M$ enemies on the map, and each enemy can be approximated as a point on the plane; the $i$-th enemy is located at $(p_i, q_i)$. JYY can use a bomb with an adjustable radius: he can set an explosion radius not exceeding $R$, then choose a point on the plane to detonate it, and all enemies within the range will be eliminated.

Of course, because the bomb is very powerful, if the explosion range touches any of JYY's buildings, then JYY's buildings will be damaged. (Note: if the explosion range only touches the boundary of a building, it will not cause damage to that building; if an enemy lies on the boundary of the explosion range, that enemy is eliminated.) JYY can freely control the detonation position and the explosion radius. As a cautious player, he wants to eliminate as many enemies as possible while ensuring that none of his buildings are damaged at all.

Input Format

The first line contains three non-negative integers $N, M, R$.

The next $N$ lines each contain three integers. The $i$-th line gives $x_i, y_i, r_i$, representing the position and radius of the $i$-th building. The testdata guarantees that no two buildings intersect (but their boundaries may touch).

The next $M$ lines each contain two integers. The $i$-th line gives $p_i, q_i$, representing the position of the $i$-th enemy. Any two enemies are at different positions, and no enemy will appear inside any building.

Output Format

Output one integer in a single line, representing the maximum number of enemies that JYY can eliminate.

1 3 3
0 0 1
3 3
-3 3
3 -3

1

1 5 3
0 0 1
3 3
-3 3
3 -3
3 0
0 3

3

4 10 100
0 0 3
10 0 3
10 10 3
0 10 3
0 4
0 5
0 6
5 3
5 -3
5 5
6 7
3 6
10 4
8 4

5

Hint

For $100\%$ of the testdata, $1 \le N \le 10$, $1 \le M \le 2000$, $1 \le R, r_i \le 2 \times 10^4$, and $|p_i|, |q_i|, |x_i|, |y_i| \le 2 \times 10^4$.

The problem is based on NAIPC 2015 Problem A - Area of Effect, with some additional self-made testdata.

Translated by ChatGPT 5