Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DRAGAOMG - Dragão de 100 Cabeças

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 Ci indicando o número de cabeças cortadas no golpe i = 1 ... G (1 ≤ Ci ≤ 150). A terceira linha contém G inteiros Ni indicando o número de cabeças que nascem após aplicado o golpe i = 1 ... G (0 ≤ Ni ≤ 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.


Adicionado por:Wanderley Guimarăes
Data:2014-05-09
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2013

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.