Minimum Overclocking Voltage for Tower Communication

There are n towers positioned along a straight road. The towers are numbered from 1 to n with positions \(a_1, a_2, \dots, a_n\) (where \(a_1 < a_2 < \cdots < a_n\)). Each tower \(i\) initially has a communication radius \(b_i\), which means tower \(i\) can transmit a signal to any tower whose position lies within \(\left[a_i - b_i,\; a_i + b_i\right]\).

However, note the special communication rule: Tower \(B\) can transmit a signal to tower \(A\) if and only if the position of tower \(A\), \(a_A\), lies within the communication range of tower \(B\); that is, \(a_A \in \left[a_B - b_B,\; a_B + b_B\right]\). In other words, even if the two ranges overlap, the signal can only be transmitted in one direction if the receiving tower’s position is inside the sender’s range.

You are allowed to apply an overclocking voltage \(k\) (where \(k\) is a non-negative integer) to all towers simultaneously. Applying a voltage \(k\) increases the communication radius of each tower by \(k\), so the new communication range of tower \(i\) becomes \(\left[a_i - (b_i+k),\; a_i + (b_i+k)\right]\).

Your goal is to determine the minimum overclocking voltage \(k\) such that a signal can be relayed sequentially from tower \(1\) to tower \(2\) to tower \(3\) and so on up to tower \(n\). In order for the signal to be transmitted from tower \(i\) to tower \(i+1\), the following condition must hold:

[ a_{i+1} \leq a_i + (b_i + k) \quad \text{for } 1 \leq i < n. ]

Determine the minimum non-negative integer \(k\) that satisfies this condition for all consecutive towers.

inputFormat

The input consists of three lines:

• The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of towers.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the positions of the towers in strictly increasing order.
• The third line contains \(n\) space-separated integers \(b_1, b_2, \dots, b_n\) representing the initial communication radius of each tower.

outputFormat

Output a single integer: the minimum non-negative overclocking voltage \(k\) required such that the signal can be relayed from tower \(1\) to tower \(n\) through consecutive towers.

sample

1
10
100

0