SPOJ Brasil

Um digrafo simples é um grafo dirigido sem arestas repetidas. Note que um digrafo simples pode ter laços (no máximo 1 por vértice) e que se a aresta (u, v) existe, a aresta (v, u) também pode existir, mas não podem haver duas ou mais arestas (u, v).

Sejam e=e₁, e₂, ..., e_n e s=s₁, s₂, ..., s_n duas sequências de inteiros não-negativos. Determine se existe ou não um digrafo simples de exatamente n vértices tal que o grau de entrada do i-ésimo vértice é e_i e o grau de saída do i-ésimo vértice é s_i.

Entrada

Há vários casos de teste.

Cada caso de teste começa com uma linha contendo um inteiro positivo n (0 < n ≤ 1000), o número de elementos nas sequências e e s. A segunda linha contém n inteiros não-negativos e₁, e₂, ..., e_n (0 ≤ e_i ≤ 1000, para todo i). A terceira linha contém n inteiros não-negativos s₁, s₂, ..., s_n (0 ≤ s_i ≤ 1000, para todo i).

A entrada termina com n = 0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo E se existe um digrafo simples que obedece às restrições propostas ou N caso contrário.

Exemplos

Entrada:
1
1
1
0

Saída:
E

O seguinte digrafo possui os graus pedidos:

Entrada:
2
0 2
0 2
0

Saída:
N

O grau de saída do segundo vértice é 2, e o grafo possui dois vértices. Logo, ele necessariamente tem que estar ligado a ambos. Mas o grau de entrada do primeiro vértice é zero, logo há uma contradição.

Entrada:
4
0 2 3 3
4 1 1 1
0

Saída:
N

A soma dos graus de entrada é 8. A soma dos graus de saída é 7. Em todo digrafo simples válido, a soma dos graus de entrada tem que ser igual à soma dos graus de saída.

Entrada:
4
3 2 1 1
4 1 1 1
0

Saída:
E

O seguinte digrafo possui os graus desejados:

Entrada:
4
1 1 2 3
0 0 3 4
3
0 2 2
2 1 1
0

Saída:
N
E