Lich's Frozen Nova

WJJ loves the game Warcraft, where the Lich is a powerful hero with the Frozen Nova ability that can kill one Elf at a time. In this problem, both Liches and Elves are represented as points on a 2D plane.

A Lich can eliminate an Elf instantly if both of the following conditions are met:

• The Euclidean distance between the Lich and the Elf satisfies $\sqrt{(x_{L}-x_{E})^2+(y_{L}-y_{E})^2} \leq r$, where $r$ is the Lich's casting range.
• The line segment connecting the Lich and the Elf does not intersect any tree (i.e. the line‐of‐sight is unobstructed).

There are $N$ Liches in the forest. After each cast of Frozen Nova, a Lich must wait for its individual cooldown time before casting again. Note that each casting can eliminate exactly one Elf.

Given the positions and parameters of the Liches, the positions of the Elves, and the descriptions of trees (each represented as a line segment), determine the minimum time required (starting from time $0$) to kill all the Elves. If it is impossible, output -1.

inputFormat

The first line contains three integers $N$, $M$, and $K$, representing the number of Liches, Elves, and Trees respectively.

Then follow $N$ lines. Each of these lines contains four numbers: x y t r, where $(x,y)$ is the position of a Lich, t is its cooldown time (the waiting time between consecutive casts), and r is its casting range.

After that, there are $M$ lines, each containing two numbers: x y, representing the position of an Elf.

Finally, there are $K$ lines, each containing four numbers: x1 y1 x2 y2. Each such line describes a tree as a line segment from $(x1,y1)$ to $(x2,y2)$.

outputFormat

Output a single integer: the minimum time required to kill all the Elves. If it is impossible, output -1.

sample

1 1 0
0 0 2 5
3 4

0