Problem C
Husdrömmar

Tyko is fast asleep, and he has a dream that he is in an $n$-dimensional space. He wants to build a house at a point in this space, and he wants to choose the location to minimize his misery of being trapped in this strange land. Building the house at a point $x \in \mathbb {R}^n$ gives him misery $M(x) = x^TFx + s^T x$, where $F$ is a symmetric $n \times n$ matrix and $s \in \mathbb {R}^n$.

There is a caveat to this though. The society in this strange land has decided that all houses must be moved some time in the future. A house at a point $p$ will be moved to the point $Ap$, where $A$ is a symmetric $n \times n$ matrix. When this move is finished, Tyko wants his house’s new coordinates to be element-wise bigger than or equal to the vector $b \in \mathbb {R}^n$. Note that he does not care about the misery level of this new position, the only important thing there is that it is at least $b$.

Input

The first line of input consists of a single integer $n$ ($2 \leq n \leq 3100$).

The second line of input contains $n$ real numbers, the elements of $b$.

The third line of input contains $n$ real numbers, the elements of $s$.

Then follow $n$ lines. The $i$th of these lines contains $i$ real numbers $A_{i1}, A_{i2}, \dots , A_{ii}$, the entries of $A$. $A$ is symmetric, so $A_{ij} = A_{ji}$.

Then follow another $n$ lines. The $i$th of these lines contains $i$ real numbers $F_{i1}, F_{i2}, \dots , F_{ii}$, the entries of $F$. $F$ is symmetric, so $F_{ij} = F_{ji}$.

All numbers in $b$, $s$, $A$ and $F$ are given with exactly $7$ digits of precision after the decimal point.

In order to generate the data, the following process was performed:

1. An integer $2 \leq n \leq 3100$ is chosen.

2. A vector $c \in \mathbb {R}^n$ is randomly generated by sampling $n$ real numbers independently of each other. The distribution is uniform between $1.0$ and $3.0$.

3. The entries of $s$ are sampled independently of each other, from a normal distribution with mean $0$ and standard deviation $\frac{1}{2}$.

4. An $n \times n$ matrix $A_0$ is generated by sampling all entries independently of each other, from a normal distribution with mean $0$ and standard deviation $\frac{1}{\sqrt{n}}$.

5. $A$ is defined as $A_0A_0^T + I$, where $I$ is the identity matrix.

6. An $n \times n$ matrix $F_0$ is generated by sampling all entries independently of each other, from a normal distribution with mean $0$ and standard deviation $\frac{1}{\sqrt{n}}$.

7. $F$ is defined as $F_0F_0^T + I$, where $I$ is the identity matrix.

8. $b$ is defined as $\frac{1}{2} AF^{-1} (Ac - s)$.

The sample test case was made by hand, but it is still possible to generate it using the process above.

Output

Print a single real number, the minimum value of $M(x)$, under the constraint that $Ax \geq b$. The program will be accepted if it is within an absolute or relative error of $10^{-5}$.

2
1.0000000 1.0000000
0.0000000 0.0000000
1.0000000
0.0000000 1.0000000
1.0000000
0.0000000 1.0000000

2.0