Minimize the Maximum Distance

Обмеження: 3 сек., 512 МіБ

This problem is different from the problem "Maximize the Minimum Distance".

There are \(n \cdot m\) points on a two-dimensional plane, located in \(n\) rows and \(m\) columns.

The distance between the \(i\)-th and the \((i+1)\)-th row is \(a_i\).

The distance between the \(i\)-th and the \((i+1)\)-th column is \(b_i\).

You want to paint all the points in some colors. The number of colors that you can use is unlimited. However, the number of points for each color you use must be two or three.

Your goal is to minimize the maximum Euclidean distance between points of the same color. You only need to find the value of the sought distance and do not need to find the actual colors of the points.

Вхідні дані

The first line contains two integers \(n\) and \(m\) – the number of rows and columns, respectively.

The second line contains \(n-1\) integers \(a_i\) – distances between the \(i\)-th and the \((i + 1)\)-th row.

The third line contains \(m-1\) integers \(b_i\) – distances between the \(i\)-th and the \((i + 1)\)-th column.

Вихідні дані

In one line print a real number – the minimum possible maximum distance between points of the same color.

Your output will be considered correct if the absolute or relative error from the true answer is at most \(10^{-7}\).

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 3 1 4 1	1.0000000000

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 3 1 1 1 1	1.4142135624

Примітки