Description

WJJ likes the game "Warcraft III." In the game, the Lich is a powerful hero whose skill Frozen Nova can kill exactly one sprite each time. We consider both liches and sprites as points on the plane.

If the Euclidean distance between a lich and a sprite does not exceed $R$, and the lich's line of sight to that sprite is not blocked by any tree (that is, the line segment between the lich and the sprite has no common point with any tree), then the lich can instantly kill that sprite.

There are $N$ liches in the forest. After casting Frozen Nova, each lich must wait for a cooldown period before casting again. Different liches have different cooldowns and cast ranges, but each cast always kills exactly one sprite.

Starting from time $0$, what is the minimum time needed to kill all the sprites?

Input Format

The first line contains three integers $N$, $M$, $K$ ($N, M, K \le 200$), representing the number of liches, sprites, and trees.

The next $N$ lines each contain four integers $x, y, r, t$, representing the coordinates, attack range, and casting interval (in seconds) of each lich.

The next $M$ lines each contain two integers $x, y$, representing the coordinates of each sprite.

The next $K$ lines each contain three integers $x, y, r$, representing the coordinates and radius of each tree.

All coordinates have absolute values at most $10000$; radii and casting intervals are at most $20000$.

Output Format

Output one line: the minimum time (in seconds) needed to eliminate all sprites. If it is impossible to eliminate all sprites, output $-1$.

2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

5

Hint

Translated by ChatGPT 5