분수 복도 건너기

현대 미술관에 흥미로운 전시가 있습니다. 정사각형 방들이 일렬로 늘어선 긴 복도인데, 각 방에는 분수가 하나씩 있습니다. 각 분수는 정수 $p$ 로 정해지며 서로 독립적으로 작동합니다. 정확히 $p$ 초 동안 켜졌다가, 정확히 $p$ 초 동안 꺼지고, 다시 켜지고 꺼지기를 영원히 반복합니다. 분수마다 $p$ 값이 다를 수 있고, $p$ 가 같아도 켜지기 시작한 시각이 달라 서로 다르게 동작할 수 있습니다.

당신은 첫 번째 방 앞에 서 있고, 복도를 가로질러 반대쪽 끝까지 가려고 합니다. 한 걸음은 정확히 $1$ 초가 걸립니다. 한 걸음에 앞으로 한 방 이동하거나(이미 끝에 도달했다면 불가), 뒤로 한 방 이동하거나(맨 앞이라면 불가), 제자리에 머무를 수 있습니다. 가능하다면 반대쪽 끝에 도달하는 가장 짧은 시간을 구하세요.

물에 젖지 않으려면, 걸음을 옮긴 직후의 그 $1$ 초 동안 분수가 꺼져 있는 방으로만 들어갈 수 있습니다. 예를 들어 어떤 분수가 시각 $0, 1, 2$ 에 켜져 있고, $3, 4, 5, 6$ 에 꺼져 있고, $7, 8, 9, 10$ 에 켜져 있고, 다시 꺼지는 식으로 반복한다고 합시다(이는 $p = 4$ 에 오프셋 $7$ 인 경우입니다). 그러면 시각 $2$ 에 그 방으로 들어가 시각 $3$ 에 도착할 수 있는데, 그때 분수가 꺼져 있기 때문입니다. 하지만 시각 $6$ 에는 들어갈 수 없습니다. 시각 $7$ 에 분수가 켜지기 때문입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 분수의 개수 $n$ 으로 시작합니다. $n = 0$ 인 줄이 나오면 입력이 끝납니다. 그 외에는 $1 \le n \le 100$ 입니다.

이어서 각 분수가 켜지고 꺼지는 시간을 나타내는 정수 $p_i$ 가 $n$ 개 주어지며, $0 \le p_i \le 10$ 입니다. $p_i = 0$ 은 $i$ 번째 분수가 고장 나 계속 꺼져 있음을 뜻합니다.

그다음 각 분수의 오프셋을 나타내는 정수 $q_i$ 가 $n$ 개 주어지며, $0 \le q_i < 2 p_i$ 입니다(고장 난 분수의 $q_i$ 는 의미가 없습니다). 이는 $i$ 번째 분수가 시각 $q_i$ 에는 켜져 있지만 그 $1$ 초 전에는 꺼져 있었음을 의미합니다.

각 테스트 케이스마다 복도의 끝에 도달하는(즉, 마지막 방 다음 자리로 들어서는) 데 필요한 가장 짧은 시간 $t$ 를 한 줄에 하나씩 출력합니다. 시각 $0$ 에 첫 번째 방 앞에 서 있다고 가정합니다(따라서 시각 $1$ 에 첫 번째 방의 분수가 꺼져 있다면 그때 들어갈 수 있습니다). 복도를 통과하는 것이 불가능하면 대신 $0$ 을 출력합니다.