Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Landmarks

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWe have an old building with *n* + 2 columns in a row. These columns support the ceiling. These columns are located in points with coordinates 0 = *x*_{0} < *x*_{1} < ... < *x*_{n} < *x*_{n + 1}. The leftmost and the rightmost columns are special, we will call them bearing, the other columns are ordinary.

For each column we know its durability *d*_{i}. Let's consider an ordinary column with coordinate *x*. Let's assume that the coordinate of the closest to it column to the left (bearing or ordinary) is *a* and the coordinate of the closest to it column to the right (also, bearing or ordinary) is *b*. In this task let's assume that this column supports the segment of the ceiling from point to point (here both fractions are considered as real division). If the length of the segment of the ceiling supported by the column exceeds *d*_{i}, then the column cannot support it and it crashes after a while, and after that the load is being redistributeed between the neighbouring columns according to the same principle.

Thus, ordinary columns will be crashing for some time until the process stops at some state. One can prove that the set of the remaining columns doesn't depend on the order in which columns crash. If there are only two bearing columns left in the end, then we assume that the whole construction crashes under the weight of the roof. But if at least one ordinary column stays in addition to the bearing ones, then the building doesn't crash.

To make the building stronger, we can add one extra ordinary column of arbitrary durability *d*' at any (not necessarily integer) point 0 < *x*' < *x*_{n + 1}. If point *x*' is already occupied by an ordinary column, it is replaced by a new one.

Your task is to find out: what minimal durability can the added column have so that the building doesn't crash?

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of ordinary columns.

The second line contains *n* + 2 integers *x*_{0}, *x*_{1}, ..., *x*_{n}, *x*_{n + 1} (*x*_{0} = 0, *x*_{i} < *x*_{i + 1} for 0 ≤ *i* ≤ *n*, *x*_{n + 1} ≤ 10^{9}) — the coordinates of the columns.

The third line contains *n* integers *d*_{1}, *d*_{2}, ..., *d*_{n} (1 ≤ *d*_{i} ≤ 10^{9}).

Output

Print a single number — the minimum possible durability of the column that you need to add in order to make the building stay. If you do not have to add the column, please print 0. Your answer will be checked with the relative or absolute error 10^{ - 4}.

Examples

Input

2

0 20 40 100

15 40

Output

10

Input

3

0 4 10 28 30

9 13 5

Output

0

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2022 04:39:01 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|