Камелот

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

Артур бажає вибрати таке місце проведення наради, щоб мінімізувати сумарні витрати лицарів, адже вони будуть відшкодовані з державної скарбниці. Це місце може знаходитись будь-де на його землях, крім границь фортець. Крім того, Артур може зменшити свої витрати, скасувавши данину не більш ніж у K вибраних ним фортецях. За свій шлях з Камелота до місця наради Король нічого не витрачає, а усі лицарі завжди вибирають найдешевший маршрут.

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

Вхідні дані

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

1. Жодні два кола, що задають фортеці, не мають спільних точок.

2. Жодні дві точки, що задають маєтки лицарів, не збігаються та не лежать на колах.

Вихідні дані

Вивести одне ціле число - мінімальну суму грошей, які Король Артур має витратити на зібрання лицарів.

Приклади