URI Online Judge | 1105

Sub-primo

Maratón de Programación SBC Brazil

Timelimit: 1

La crisis económica mas reciente fue causada parcialmente por la manera en la que los bancos daban préstamos a personas que no podían pagarlos y luego los revendian a otros bancos como bonos. Obviamente, cuando la gente no pudo pagar sus préstamos, el sistema colapsó.

La crisis fue tan profunda que afectó a países de todo el mundo, incluyendo Nlogonia, donde el honorable primer ministro Man Dashuva ordenó al presidente del Banco Central dar una solucion al problema. Al presidente se le ocurrió una idea brillante: si todos los bancos pueden liquidar sus bonos con sus reservas monetarias, todos los bancos pueden sobrevivir y la crisis puede ser evitada.

Sin embargo, con el número elevado de bonos y bancos involucrados, esta tarea fue extremadamente difícil, por lo que pide tu ayuda para hacer un programa que, dados los bancos y los bonos impresos por ellos, determine si es posible que todos los bancos paguen sus deudas utilizando sólo sus reservas monetarias y créditos.

Entrada

La entrada consiste de varios casos de prueba. La primer línea de cada caso de prueba contiene dos enteros B and N, que indican el número de bancos (1 ≤ B ≤ 20) y el número de bonos impresos por ellos (1 ≤ N ≤ 20). Los bancos son identificados por enteros entre el 1 y B. La segunda línea contiene B enteros Ri separados por espacios, indicando las reservas monetarias de cada uno de los B bancos (0 ≤ Ri ≤ 104, para 1 ≤ iB). Las N líneas siguientes contienen cada una tres enteros separados por espacios: un entero D, indicando el banco deudor (1 ≤ DB), un entero C , indicando el banco creditor (1 ≤ CB e DC) y un entero V, indicando el valor de los bonos (1 ≤ V ≤ 104).

El final de la entrada es indicado por una línea conteniendo solamente dos ceros, separados por espacios.

Salida

Para cada caso de prueba, el programa debe imprimir una sola línea, conteniendo un solo caracter: 'S', si es posible liquidar todos los bonos sin un rescate financiero del Banco Central de Nlogonia, ó 'N' si el rescate es necesario.

Ejemplos de Entrada Ejemplos de Salida

3 3

1 1 1
1 2 1
2 3 2
3 1 3
3 3
1 1 1
1 2 1
2 3 2
3 1 4
3 3
1 1 1
1 2 2
2 3 2
3 1 2
0 0

S

N

S