Camelot#4979

Camelot

1 second

256 megabytes

Very hard

King Arthur has summoned his knights for an urgent military council. In his realm, there are defensive fortresses arranged in a circular pattern, renowned for their impregnability. Some fortresses are nested within others, offering additional protection. When knights receive Arthur's orders, they travel from their estates with their guards. If a knight's journey takes him from outside a fortress to inside, or vice versa, he must pay a toll at the gate. Each fortress sets its toll per person, so the knight must pay for himself and his guards.

Arthur aims to select a meeting location that minimizes the knights' total expenses, as these costs will be reimbursed from the state treasury. The meeting place can be anywhere on his lands, except on the boundaries of the fortresses. Additionally, Arthur can reduce expenses by waiving the toll in up to $K$ fortresses of his choice. For his own journey from Camelot to the meeting place, the King incurs no expenses, and all knights will always choose the least costly route.

Your task is to write a program that, given the map of Arthur's lands, the toll amounts for each fortress, the number of guards with each knight, and the number of fortresses where the toll can be waived, determines the minimum amount of money needed to hold the council. The map is represented as a plane with circles indicating fortresses and points indicating knights' estates.

Input

The first line contains three integers $N$ , $M$ , and $K$ ( $2 \leq N \leq 35000$ 2 \le N \le 35000, $1 \leq M \leq 35000$ 1 \le M \le 35000, $0 \leq K \leq N$ 0 \le K \le N), where $N$ is the number of fortresses, $M$ is the number of knights summoned, and $K$ is the number of fortresses where Arthur can cancel the toll. The next $N$ lines describe the fortresses, each containing four integers $x$ , $y$ , $R$ , $C$ ( $- 1 0^{6} \leq x \leq 1 0^{6}$ -10^6 \le x \le 10^6, $- 1 0^{6} \leq y \leq 1 0^{6}$ -10^6 \le y \le 10^6, $1 \leq R \leq 2 \cdot 1 0^{6}$ 1 \le R \le 2 \cdot 10^6, $1 \leq C \leq 1 0^{5}$ 1 \le C \le 10^5), where $(x, y)$ are the coordinates of the fortress center, $R$ is the radius, and $C$ is the toll per person. The next $M$ lines provide information about the knights, each containing three integers $x$ , $y$ , $L$ ( $- 1 0^{6} \leq x \leq 1 0^{6}$ -10^6 \le x \le 10^6, $- 1 0^{6} \leq y \leq 1 0^{6}$ -10^6 \le y \le 10^6, $1 \leq L \leq 1 0^{5}$ 1 \le L \le 10^5), where $(x, y)$ are the coordinates of the knight's estate, and $L$ is the number of guards traveling with the knight, including himself. It is guaranteed that:

No two circles representing fortresses overlap.
No two points representing knights' estates coincide or lie on the circles.

Output

Output a single integer - the minimum amount of money King Arthur needs to spend to gather the knights.

Examples

Example 1