Hall of Fountains

The Museum of Modern Art has an exciting exhibition: a long hall made of a sequence of square rooms, and every room holds a water fountain. Each fountain is described by a number $p$ and behaves independently of the others: it stays on for exactly $p$ seconds, then off for exactly $p$ seconds, then on again, then off again, and so on forever. Different fountains may have different values of $p$, and even fountains that share the same $p$ may behave differently because they were started at different moments.

You stand in front of the first room and want to cross the hall to the far end. Each of your steps takes exactly $1$ second. In one step you may move one room forward (unless you are already at the far end), one room backward (unless you are at the very beginning), or stay where you are. Compute the shortest time to reach the far end, if it is possible at all.

Because you do not want to get wet, you may only move into a room whose fountain is off during the second right after your step. For example, suppose a fountain is on at times $0, 1, 2$, off at times $3, 4, 5, 6$, on at times $7, 8, 9, 10$, off again, and so on (this corresponds to $p = 4$ with an offset of $7$). Then you may step into that room at time $2$, arriving at time $3$, when the fountain is off. But you may not step into it at time $6$, because at time $7$ it would be on.

The input contains several test cases. Each test case begins with the number of fountains $n$. The input ends with a line containing $n = 0$. Otherwise $1 \le n \le 100$.

Next come $n$ integers $p_i$, the on/off duration of each fountain, with $0 \le p_i \le 10$. A value $p_i = 0$ means fountain $i$ is out of order and stays off forever.

Then come $n$ integers $q_i$, the offset of each fountain, with $0 \le q_i < 2 p_i$ (for an out-of-order fountain $q_i$ is meaningless). It means fountain $i$ is on at time $q_i$ but was off one second earlier.

For each test case, output a single integer $t$ on its own line: the shortest time needed to reach the end of the hall (that is, to enter the space past the last room). Assume you are in front of the first room at time $0$ (so you may enter the first room at time $1$ if its fountain is off at time $1$). If it is impossible to cross the hall, print $0$ instead.