eolymp
bolt
Try our new interface for solving problems
Problems

Камелот

Камелот

Time limit 1 second
Memory limit 256 MiB

Король Артур решил собрать рыцарей для срочного военного совета. На землях, которыми правил Артур, находились оборонные крепости, построенные в форме окружности, — такие считались наиболее неприступными. Некоторые крепости находились внутри других, что обеспечивало им еще большую защищенность. Как только рыцари получают приказ от Артура, они отправляются в дорогу из своего имения в сопровождении охраны. Если путь рыцаря проходит снаружи крепости внутрь или наоборот, он должен заплатить дань за прохождение через ворота. Каждая крепость устанавливает размер дани за проход одного человека, то есть рыцарю нужно заплатить за себя и своих охранников.

Артур желает выбрать такое место проведения совета, чтобы минимизировать суммарные затраты рыцарей, ведь они будут возмещены из государственной казны. Это место может находиться где угодно на его землях, кроме границ крепостей. Кроме того, Артур может уменьшить свои расходы, отменив дань не более чем в K выбранных им крепостях. На свой путь из Камелота до места совета Король ничего не тратит, а все рыцари всегда выбирают самый дешевый маршрут.

Напишите программу, которая по информации о карте земель Артура, размеры дани каждой из крепостей, количестве охранников у рыцарей и количестве крепостей, где дань может быть отменена по приказу Короля, найдет минимальное количество денег, которые он должен потратить для проведения совета. Карта земель может быть представлена в виде плоскости с окружностями, которые задают крепости, и точками, которые задают имения рыцарей.

Input data

Первая строка содержит три целых числа N, M и K (2 N 35000, 1 M 35000, 0 K N), где N - количество крепостей на землях Артура, M - количество рыцарей, вызванных на совет, а K - количество крепостей, в которых Артур может отменить дань. Последующие N строк задают крепости и содержат по четыре целых числа: x, y, R, C (-10^6x 10^6, -10^6y 10^6, 1 R 2∙10^6, 1 C 10^5), где (x, y) - координаты центра крепости на карте, R - радиус окружности, которая задает крепость, и C - размер дани с человека. Последующие M строк задают данные о рыцарях и содержат по три целых числа: x, y, L (-10^6x 10^6, -10^6y 10^6, 1 L 10^5), где (x, y) - координаты имения рыцаря на карте, L - количество охранников, которые путешествуют вместе с рыцарем, включая самого рыцаря. Гарантируется, что:

  1. Никакие две окружности, которые задают крепости, не имеют общих точек.

  2. Никакие две точки, которые задают имения рыцарей, не совпадают и не лежат на окружностях.

Output data

Вывести одно целое число - минимальную сумму денег, которые Король Артур должен потратить, чтобы собрать рыцарей.

Examples

Input example #1
4 9 1
6 10 2 1
5 4 2 1
10 7 1 200
7 7 7 1
5 3 10
6 10 1
7 10 1
10 7 1
10 10 1
9 11 1
9 12 1
13 1 1
14 1 1
Output example #1
12
Author Roman Edemskiy
Source 2013 XXVI All-Ukrainian Informatics Olympiad, Lugansk, March 17 - 21, Round 2