Нехай буде світло
Ви хочете, щоб загальна інтенсивність освітлення в об'єктивній точці була максимальною. Для цього можна видалити деякі повітряні кулі, які заважають світлу. Однак через вартість видалення існує обмеження на кількість куль, які можна видалити. Отже, ви прагнете видалити такий набір куль, щоб максимізувати інтенсивність освітлення в об'єктивній точці.
Наступна ілюстрація демонструє конфігурацію, описану в першому наборі даних зразка введення, наведеного нижче. На рисунку показана xy-площина, що є достатньою, оскільки в цьому наборі даних z-координати всіх джерел світла, центрів куль і об'єктивної точки дорівнюють нулю. На рисунку джерела світла зображені як зірки, а кулі як кола. Об'єктивна точка знаходиться в початку координат, і ви можете видалити до 4 куль. У цьому випадку пунктирні кола на рисунку відповідають кулям, які потрібно видалити.
Рисунок 1: Перший набір даних зразка введення.
Вхідні дані
Вхідні дані складаються з кількох наборів. Кожен набір даних має такий формат:
N M R
S_1x S_1y S_1z S_1r
...
S_Nx S_Ny S_Nz S_Nr
T_1x T_1y T_1z T_1b
...
T_Mx T_My T_Mz T_Mb
E_x E_y E_z
Перша строка набору даних містить три додатні цілі числа, N, M і R, розділені пробілом. N означає кількість куль, яка не перевищує 2000. M означає кількість джерел світла, яка не перевищує 15. R означає кількість куль, які можуть бути видалені, що не перевищує N.
Кожна з N наступних строк містить чотири цілі числа, розділені пробілом. (S_ix, S_iy, S_iz) означає положення центру i-ї кулі, а S_ir означає її радіус.
Кожна з наступних M строк містить чотири цілі числа, розділені пробілом. (T_jx, T_jy, T_jz) означає положення j-го джерела світла, а T_jb означає його яскравість.
Остання строка набору даних містить три цілі числа, розділені пробілом. (E_x, E_y, E_z) означає положення об'єктивної точки.
S_ix, S_iy, S_iz, T_jx, T_jy, T_jz, E_x, E_y і E_z більше ніж -500, і менше ніж 500. S_ir більше ніж 0, і менше ніж 500. T_jb більше ніж 0, і менше ніж 80000.
В об'єктивній точці інтенсивність світла від j-го джерела світла обернено пропорційна квадрату відстані, а саме
якщо немає кулі, що перериває світло. Загальна інтенсивність освітлення є сумою вищезазначеного.
Ви можете припустити наступне.
Відстань між об'єктивною точкою та будь-яким джерелом світла не менше ніж 1.
Для кожного i і j, навіть якщо S_ir змінюється на ϵ (|ϵ| < 0.01), чи приховує i-та куля j-те світло чи ні, не змінюється.
Кінець введення позначається строкою з трьох нулів.
Вихідні дані
Для кожного набору даних виведіть рядок, що містить десятковий дріб, який означає найвищу можливу інтенсивність освітлення в об'єктивній точці після видалення R куль. Вихід не повинен містити помилку більше ніж 0.0001.