Камелот
Kral Artur təcili hərbi müşavirə üçün cəngavərləri toplamağa qərar verdi. Arturun idarə etdiyi torpaqlarda dairəvi şəkildə tikilmiş müdafiə qalaları mövcuddur və bunlar ən keçilməz hesab olunur. Bəzi qalalar digərlərinin içərisində yerləşir, bu da onlara əlavə müdafiə təmin edir. Cəngavərlər Arturdan əmr aldıqdan sonra mühafizəçiləri ilə birlikdə mülkündən yola çıxırlar. Əgər cəngavərin yolu qaladan içəriyə və ya əksinə keçirsə, o, qapıdan keçmək üçün vergi ödəməlidir. Hər bir qala bir nəfərin keçidi üçün verginin miqdarını müəyyən edir, yəni cəngavər özü və mühafizəçiləri üçün ödəməlidir.
Artur müşavirənin keçirilməsi üçün elə bir yer seçmək istəyir ki, cəngavərlərin ümumi xərclərini minimuma endirsin, çünki bu xərclər dövlət xəzinəsindən ödəniləcək. Bu yer qalaların sərhədləri istisna olmaqla onun torpaqlarında hər yerdə ola bilər. Bundan əlavə, Artur seçdiyi ən çox K qalada vergini ləğv etməklə xərcləri azalda bilər. Kamelotdan müşavirə yerinə gedən yolda Kral heç bir xərc çəkmir və bütün cəngavərlər həmişə ən ucuz marşrutu seçirlər.
Arturun torpaqlarının xəritəsi, hər bir qalanın vergi miqdarı, cəngavərlərin mühafizəçilərinin sayı və Kralın əmri ilə vergini ləğv edə biləcəyi qalaların sayı haqqında məlumatlara əsasən, müşavirənin keçirilməsi üçün sərf etməli olduğu minimum pul miqdarını tapacaq bir proqram yazın. Torpaqların xəritəsi qalaları təyin edən dairələr və cəngavərlərin mülklərini təyin edən nöqtələr şəklində təmsil oluna bilər.
Giriş verilənləri
Birinci sətir üç tam ədəd N, M və K (2 ≤ N ≤ 35000, 1 ≤ M ≤ 35000, 0 ≤ K ≤ N) ehtiva edir, burada N - Arturun torpaqlarında olan qalaların sayı, M - müşavirəyə çağırılan cəngavərlərin sayı, K - Arturun vergini ləğv edə biləcəyi qalaların sayı. Növbəti N sətir qalaları təyin edir və dörd tam ədəd x, y, R, C (-10^6 ≤ x ≤ 10^6, -10^6 ≤ y ≤ 10^6, 1 ≤ R ≤ 2∙10^6, 1 ≤ C ≤ 10^5) ehtiva edir, burada (x, y) - xəritədə qalanın mərkəzinin koordinatları, R - qalayı təyin edən dairənin radiusu və C - bir nəfər üçün verginin miqdarıdır. Növbəti M sətir cəngavərlər haqqında məlumatları təyin edir və üç tam ədəd x, y, L (-10^6 ≤ x ≤ 10^6, -10^6 ≤ y ≤ 10^6, 1 ≤ L ≤ 10^5) ehtiva edir, burada (x, y) - xəritədə cəngavərin mülkünün koordinatları, L - cəngavərlə birlikdə səyahət edən mühafizəçilərin sayı, cəngavər də daxil olmaqla. Zəmanət verilir ki:
Qalaları təyin edən heç bir iki dairə ortaq nöqtəyə malik deyil.
Cəngavərlərin mülklərini təyin edən heç bir iki nöqtə üst-üstə düşmür və dairələr üzərində yerləşmir.
Çıxış verilənləri
Bir tam ədəd çıxarın - Kral Arturun cəngavərləri toplamaq üçün sərf etməli olduğu minimum pul miqdarı.