SP15733 ULM2H - Hall of Fountains

The Museum of Modern Art has a really exciting exhibition: a kind of a longish hall composed of a sequence of quadratic-shaped rooms. Each room is equipped with a water fountain. Each fountain is characterized by a number _p_ and acts independent of the others. It will be turned on for exactly _p_ seconds, then it will be turned off for exactly _p_ seconds, then on again, then off again, and so on for good. However, different fountains may have different values of _p_. And even if they share the same value, they still may perform not identically, for they might have been started at different times. You stand in front of the first room, and want to cross the hall to the other end. Each of your steps takes exactly 1 second. You are able to move one room forward (unless you already reached the other end), one room backward (unless you are at the beginning), or just stay at your current position. Calculate the shortest time to reach the other end, if it is possible at all. Since you do not want to get wet, you can only move into a room where the water fountain will be off during the second after your step. For example, suppose that the fountain in the next room behaves so, that it is on at times 0, 1, 2, then off at times 3, 4, 5, 6, then on at times 7, 8, 9, 10, then off again (which indicates _p=4_ with an offset of 7). Then, you can move at time 2 into the room, arriving there at time 3, when the fountain is off. But you cannot move at time 6 into the room, because at time 7 it will be on. **Input Specification** The input contains several test cases. Each test case starts with the number of fountains _n_. Input is terminated by _n=0_. Otherwise, _1. Then follow _n_ numbers _p $ _{i} $_ denoting the time each fountain is on and off, where _0. A value of 0 for _p $ _{i} $_ indicates that fountain _i_ is out of order (i.e. constantly off). Then follow _n_ numbers _q $ _{i} $_ denoting the offset of each fountain, where _0, unless the fountain is out of order, in which case _q $ _{i} $_ is meaningless. Otherwise it means that fountain _i_ will be on at time _q $ _{i} $_ , but off just one second before.___ **Output Specification** For each test case output on a line a single number _t_ denoting the shortest time needed to reach the end of the hall (i.e. to enter the place after the last room). Assume, that you are in front of the first room at time 0 (i.e. you can enter the first room at time _1_, if the fountain is off at time _1_). If it is impossible to go through the hall of fountains, print 0 instead. **Sample Input** ``` 3 0 0 0 0 0 0 4 6 3 3 4 2 3 0 4 2 1 1 0 0 0 ``` **Sample Output** ``` 4 11 0 ```

N/A

N/A