Атака на велетенського n-пуса#3115
Піратський корабель атакує велетенський -пус^{1}. щупалець і голова істоти проштрикнули палубу й сіють хаос на кораблі. Намагаючись зупинити істоту, щоб вона не знищила корабель, капітан кидається до її голови. На жаль, його швидко відкидає одне зі щупалець. Капітан розуміє, що не може атакувати голову -пуса, поки щупальця рухаються вільно.
На щастя, капітан не сам на кораблі. На палубі перебувають піратів (p \geq n), які готові виконувати накази капітана. Капітан вигадує такий план: якщо кожне щупальце буде атаковане одним піратом, він зможе безперешкодно дістатися до голови істоти й добити її. Для безпеки капітан почне рухатись лише після того, як кожне щупальце буде атаковане піратом. Щойно капітан дістанеться голови, він зможе миттєво вбити істоту. Капітан хоче визначити, яких піратів до яких щупалець відправити, щоб убити істоту якомога швидше. Оскільки така ситуація трапляється регулярно, капітан просить вас написати програму для розв'язання цієї задачі.
____________ ^{1} -пус — це як восьминіг, але з щупальцями.
У першому рядку задано кількість тестів. Кожен тест складається з:
Один рядок з двома цілими числами і (1 \leq n \leq p \leq 100): кількість щупалець у -пуса та кількість піратів (без урахування капітана).
Один рядок із трьома цілими числами x_c, y_c і v_c: координати й швидкість капітана.
рядків по три цілі числа x_i, y_i і v_i: координати й швидкість кожного пірата.
Один рядок із двома цілими числами x_h і y_h: координати голови -пуса.
рядків по два цілі числа x_j і y_j: координати кожного щупальця.
Усі координати задовольняють 0 \leq x, y \leq 10000. Усі швидкості задовольняють 1 \leq v \leq 100.
Капітан, пірати, голова й щупальця вважаються точковими (тобто не мають розмірів). Усі позиції різні.
Капітан і всі пірати рухаються до цілей по прямій із власною сталою швидкістю, без жодних перешкод.
Для кожного тесту виведіть одне дійсне число в окремому рядку — мінімальний час, потрібний капітану, щоб убити -пуса. Ваша відповідь має бути з абсолютною або відносною похибкою не більше 10^{-6}.
Приклад 1