Problema D: Não metas água!


image jarros
Imaginemos que temos de medir 1L (um litro) de água, mas só temos dois jarros, um de 3L e outro de 2L . Uma solução será encher o jarro de 3L de uma torneira, depois o de 2L com a água do primeiro, que ficará exatamente com 1L . Mas se tivermos um jarro de 5L e outro de 2L? Podemos encher o de 5L da torneira, encher o de 2L com esta água, esvaziar esse jarro na pia, e voltar a enchê-lo com os 3L remanescentes do jarro maior, que fica apenas com 1L.

Estes puzzles, que requerem medir volumes usando vários jarros não graduados, são um clássico em Inteligência Artificial. Podemos recorrer apenas a operações de três tipos: encher completamente um jarro a partir de uma torneira; esvaziar completamente um jarro para uma pia; ou encher um jarro com o conteúdo de outro. Neste último caso, ou o jarro que recebe a água fica completamente cheio, ou o jarro que fornece a água fica completamente vazio.

No final de uma sequência de operações destas, um dos jarros deverá ter um determinado volume alvo. Estes volumes, quer o alvo, quer a capacidade dos jarros, costumam ser valores inteiros positivos, todos na mesma unidade (litro, por exemplo).

Tarefa

Escreva um programa que recebe a descrição de um puzzle e uma sequência de operações, e determina se essa sequência é uma solução do puzzle, ou não.

Input

O input começa com a descrição do puzzle, que é seguida por uma sequência de operações.

A descrição do puzzle começa com N+1 linhas, cada uma com um único inteiro. As primeiras N linhas têm as capacidades Ci dos N jarros, ou seja, o número na i-ésima linha representa a capacidade do jarro número i (para i=1,2,…,N). A última destas linhas tem o valor 0. Segue-se uma linha com um inteiro A, que é o alvo a atingir.

Finalmente, as operações são descritas por S linhas, cada uma com dois inteiros, F e D, em que F representa a fonte da água e D o destino dessa água, com o seguinte significado:

F=0 a fonte da água é a torneira;
0<F≤N a fonte da água é o jarro número F;
D=0 o destino da água é a pia;
0<D≤N o destino da água é o jarro número D.
Esta sequência termina com uma linha com dois zeros (0 0).

Restrições

  2≤N<10 Número de jarros
  1≤A<10 Alvo a atingir
  1≤Ci<10 Capacidade do jarro número i (para i=1,2,…,N)
  0≤F≤N Fonte da água numa operação
  0≤D≤N Destino da água numa operação
  1≤S≤15 Tamanho da sequência de operações

Output

O output deve ter uma única linha com uma única palavra, em maiúsculas: "CERTO", se a sequência de operações for uma solução do puzzle; "ERRADO", no caso contrário.

Exemplo 1

Input 

2
3
0
1
0 2
2 1
0 0

Output 

CERTO

Exemplo 2

Input 

5
2
0
1
0 1
1 2
2 0
1 2
0 0

Output 

CERTO

Exemplo 3

Input 

3
6
9
0
2
0 1
1 2
2 0
0 0

Output 

ERRADO


ToPAS'2024