Camelot
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 ≤ N ≤ 35000, 1 ≤ M ≤ 35000, 0 ≤ K ≤ 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 (-10^6 ≤ x ≤ 10^6, -10^6 ≤ y ≤ 10^6, 1 ≤ R ≤ 2∙10^6, 1 ≤ C ≤ 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 (-10^6 ≤ x ≤ 10^6, -10^6 ≤ y ≤ 10^6, 1 ≤ L ≤ 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.
