Tower Communication Enhancement

There are \(n\) towers placed along a straight road, numbered \(1, 2, \dots, n\), located at positions \(a_1, a_2, \dots, a_n\) with \(a_1 < a_2 < \dots < a_n\). Each tower \(i\) has an initial communication radius \(b_i\), meaning that tower \(i\) can transmit signals to any tower whose position lies within the interval \(\left[a_i - b_i,\; a_i + b_i\right]\).

Important: For any two towers \(A\) and \(B\), tower \(B\) can transmit a signal to tower \(A\) if and only if the position of tower \(A\) is within the communication range of tower \(B\). In other words, even if the communication ranges overlap, communication is only possible in the direction where the receiving tower lies inside the sender's range.

You are allowed to overclock (boost) all towers simultaneously by applying an extra voltage \(k\) (where \(k\) is a nonnegative integer). This increases the communication radius of every tower by \(k\), so tower \(i\) can then transmit to towers within \(\left[a_i - (b_i+k),\; a_i + (b_i+k)\right]\).

Your task is to compute the minimum \(k\) required so that there exists a sequence of transmissions (using one or more towers as intermediaries) to relay a signal from tower \(1\) to tower \(n\).

inputFormat

The input consists of three lines:

1. The first line contains a single integer \(n\) representing the number of towers.
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the positions of the towers in increasing order.
3. The third line contains \(n\) space-separated integers \(b_1, b_2, \dots, b_n\) representing the initial communication radii of the towers.

outputFormat

Output a single integer, the minimum nonnegative integer \(k\) required so that a signal can be relayed from tower \(1\) to tower \(n\).

sample

3
1 3 6
1 1 1

3