Мінімізуйте максимальну відстань#12963

Мінімізуйте максимальну відстань

3 секунди
512 мегабайтів
Дуже складна

Ця задача відрізняється від задачі "Максимізуйте мінімальну відстань".

На двовимірній площині розташовано n \cdot m точок, організованих у рядків та стовпців.

Відстань між -м та (i+1)-м рядками дорівнює a_i.

Відстань між -м та (i+1)-м стовпцями дорівнює b_i.

Вам потрібно розфарбувати всі точки у деякі кольори. Кількість кольорів, які можна використовувати, не обмежена. Проте кожен використаний колір має відповідати рівно двом або трьом точкам.

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

Вхідні дані

У першому рядку задано два цілі числа та — кількість рядків і стовпців відповідно.

У другому рядку задано n-1 цілих чисел a_i — відстані між -м та (i + 1)-м рядками.

У третьому рядку задано m-1 цілих чисел b_i — відстані між -м та (i + 1)-м стовпцями.

2 \le n, m \le 3 \cdot 10^5,

1 \le a_i, b_i \le 10^9.

Вихідні дані

В одному рядку виведіть дійсне число — мінімально можливу найбільшу відстань між точками одного кольору.

Ваша відповідь вважатиметься правильною, якщо абсолютна або відносна похибка не перевищуватиме 10^{-7}.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

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

У другому прикладі ми розфарбовуємо точки у чотири кольори: три точки мають блакитний колір, а по дві точки — зелений, червоний та коричневий. Відстань між двома найвіддаленішими блакитними точками дорівнює \sqrt{2}. Також дві зелені точки знаходяться на відстані \sqrt{2} одна від одної. Відповідь для цього прикладу дорівнює \sqrt{2}.