Нехай буде світло#5418

Нехай буде світло

30 секунд

128 мегабайтів

Дуже складна

Ви хочете, щоб загальна інтенсивність освітлення в об'єктивній точці була максимальною. Для цього можна видалити деякі повітряні кулі, які заважають світлу. Однак через вартість видалення існує обмеження на кількість куль, які можна видалити. Отже, ви прагнете видалити такий набір куль, щоб максимізувати інтенсивність освітлення в об'єктивній точці.

Наступна ілюстрація демонструє конфігурацію, описану в першому наборі даних зразка введення, наведеного нижче. На рисунку показана $x y$ -площина, що є достатньою, оскільки в цьому наборі даних $z$ -координати всіх джерел світла, центрів куль і об'єктивної точки дорівнюють нулю. На рисунку джерела світла зображені як зірки, а кулі як кола. Об'єктивна точка знаходиться в початку координат, і ви можете видалити до $4$ куль. У цьому випадку пунктирні кола на рисунку відповідають кулям, які потрібно видалити.

Рисунок 1: Перший набір даних зразка введення.

Вхідні дані

Вхідні дані складаються з кількох наборів. Кожен набір даних має такий формат:

$N$ $M$ $R$

$S_{1 x}$ S_{1x} $S_{1 y}$ S_{1y} $S_{1 z}$ S_{1z} $S_{1 r}$ S_{1r}

$\dots$

$S_{N x}$ S_{Nx} $S_{N y}$ S_{Ny} $S_{N z}$ S_{Nz} $S_{N r}$ S_{Nr}

$T_{1 x}$ T_{1x} $T_{1 y}$ T_{1y} $T_{1 z}$ T_{1z} $T_{1 b}$ T_{1b}

$\dots$

$T_{M x}$ T_{Mx} $T_{M y}$ T_{My} $T_{M z}$ T_{Mz} $T_{M b}$ T_{Mb}

$E_{x}$ E_x $E_{y}$ E_y $E_{z}$ E_z

Перший рядок набору даних містить три додатні цілі числа, $N$ , $M$ і $R$ , розділені пробілом. $N$ означає кількість куль, яка не перевищує $2000$ . $M$ означає кількість джерел світла, яка не перевищує $15$ . $R$ означає кількість куль, які можуть бути видалені, що не перевищує $N$ .

Кожен з $N$ наступних рядків містить чотири цілі числа, розділені пробілом. $(S_{i x}, S_{i y}, S_{i z})$ (S_{ix}, S_{iy}, S_{iz}) означає положення центру $i$ -ї кулі, а $S_{i r}$ S_{ir} означає її радіус.

Кожен з наступних $M$ рядків містить чотири цілі числа, розділені пробілом. $(T_{j x}, T_{j y}, T_{j z})$ (T_{jx}, T_{jy}, T_{jz}) означає положення $j$ -го джерела світла, а $T_{j b}$ T_{jb} означає його яскравість.

Останній рядок набору даних містить три цілі числа, розділені пробілом. $(E_{x}, E_{y}, E_{z})$ (E_x, E_y, E_z) означає положення об'єктивної точки.

$S_{i x}$ S_{ix}, $S_{i y}$ S_{iy}, $S_{i z}$ S_{iz}, $T_{j x}$ T_{jx}, $T_{j y}$ T_{jy}, $T_{j z}$ T_{jz}, $E_{x}$ E_x, $E_{y}$ E_y і $E_{z}$ E_z більше ніж $- 500$ , і менше ніж $500$ . $S_{i r}$ S_{ir} більше ніж $0$ , і менше ніж $500$ . $T_{j b}$ T_{jb} більше ніж $0$ , і менше ніж $80000$ .

В об'єктивній точці інтенсивність світла від $j$ -го джерела світла обернено пропорційна квадрату відстані, а саме

якщо немає кулі, що перериває світло. Загальна інтенсивність освітлення є сумою вищезазначеного.

Ви можете припустити наступне.

Відстань між об'єктивною точкою та будь-яким джерелом світла не менше ніж $1$ .
Для кожного $i$ і $j$ , навіть якщо $S_{i r}$ S_{ir} змінюється на $ϵ$ ( $∣ ϵ ∣ < 0.01$ |\epsilon| < 0.01), чи приховує $i$ -та куля $j$ -те світло чи ні, не змінюється.

Кінець введення позначається рядком з трьох нулів.

Вихідні дані

Для кожного набору даних виведіть рядок, що містить десятковий дріб, який означає найвищу можливу інтенсивність освітлення в об'єктивній точці після видалення $R$ куль. Вихід не повинен містити помилку більше ніж $0.0001$ .

Приклади

Приклад 1