Dams

A large water reservoir was built in Byteotia. It is divided into several sectors of equal length. Between every two neighboring sectors stands a dam of some height, and dams also stand in front of the first sector and behind the last sector.

At this moment the water level is the same across the whole reservoir. But heavy rain has begun and the water level is rising fast. The king wants to know how long it will take before water spills over the first dam or the last dam, which would surely flood the whole country. The calculation is tricky because the rain may fall with a different intensity over each sector.

Compute the time left until water spills out of the reservoir. If the water level is exactly equal to a dam's height, the water is not yet spilling. When a flooded part of the reservoir is bounded on both sides by dams of the same height, water spills from it to both sides equally fast.

The first line contains one integer $n$ ($1 \le n \le 500\,000$), the number of sectors the reservoir is divided into.

The second line contains $n+1$ integers $w_i$ ($1 \le w_i \le 1\,000\,000$) separated by single spaces, giving the heights of the successive dams from left to right, measured above the initial water level.

The third line contains $n$ integers $k_i$ ($1 \le k_i \le 1\,000\,000$) separated by single spaces, where $k_i$ is the number of levels by which the water in the $i$-th sector rises during one second.

Print one integer: the smallest integer not smaller than the number of seconds after which water spills out of the reservoir.