SPOJ Brasil

Em seu caminho para salvar uma princesa, um cavaleiro encontra um dragão de 100 cabeças. Com um golpe de espada ele pode cortar 7, 11, ou 15 cabeças. Porém, para cada um desses golpes, novas cabeças nascem imediatamente (respectivamente 10, 16 e 11). Em outras palavras, se ele cortar 7 cabeças, nascem 10 novas. Se ele cortar 11 nascem 16, e se ele cortar 15 nascem 11.

O dragão morre apenas se ficar sem cabeça, ou seja, se for aplicado um golpe que corta todas as cabeças restantes (nesse caso não nascem novas cabeças). Quantos golpes o cavaleiro precisa para matar o dragão e assim salvar a princesa?

Observações

Se durante a sequência de golpes o dragão ficar com mais de 1.000 cabeças, ele mata o cavaleiro. O cavaleiro também morre se não conseguir matar o dragão.

Um golpe só pode ser aplicado se houver cabeças suficientes. Por exemplo, o golpe que corta 7 cabeças não pode ser aplicado num momento em que o dragão tiver menos de 7 cabeças.

Entrada

A entrada contém vários casos de teste, cada um representando os possíveis golpes do cavaleiro para matar o dragão de 100 cabeças. A primeira linha de um caso de teste contém um inteiro G que representa o número de golpes diferentes (1 ≤ G ≤ 10). A segunda linha contém G inteiros C_i indicando o número de cabeças cortadas no golpe i = 1 ... G (1 ≤ C_i ≤ 150). A terceira linha contém G inteiros N_i indicando o número de cabeças que nascem após aplicado o golpe i = 1 ... G (0 ≤ N_i ≤ 100). A entrada termina quando G = 0.

Saída

Para cada caso de teste da entrada escreva uma linha contendo o número mínimo de golpes necessários para matar o dragão. Se não for possível matar o dragão com os golpes indicados escreva “cavaleiro morreu”.

Exemplos

Entrada:
3
7 11 15
10 16 11
4
15 17 20 5
24 2 14 17
1
20
10
0

Saída:
24
cavaleiro morreu
9

No primeiro exemplo, o cavaleiro consegue matar o dragão com 24 golpes, aplicando 22 golpes que cortam 15 cabeças (o dragão ficará com 12 cabeças), um golpe que corta 7 cabeças (e então ele ficará com 15 cabeças), e finalmente um que corta as 15 cabeças restantes.