Después de que los héroes ninjas derrotaran a ByteZap, el día de la desaparición, MegaBit tuvo que mantener a las muñecas en el museo. Entre estas muñecas hay ~m~ corredores que pueden circular en ambas direcciones. Se garantiza que en los pasillos ~m~ MegaBit puede alcanzar cada una de las ~n~ muñecas. GigaBit, teniendo cinco tipos de obstáculos ~A, B, C, D, E~, intenta detener a MegaBit colocando cuatro obstáculos en cada corredor. MegaBit puede destruir obstáculos de tipo ~A, B, C~ y ~D~, pero no puede destruir obstáculos de tipo ~E~. Para destruir un obstáculo de tipo ~A~, el arma de MegaBit necesita ~1~ unidad de energía para destruir un obstáculo de tipo ~B~ de ~2~ unidades de energía para destruir un obstáculo tipo ~C~ de ~3~ unidades de energía y para destruir un obstáculo Tipo ~D~ de ~4~ unidades de energía. Debido al dispositivo con el que GigaBit coloca los obstáculos en el corredor, los cuatro obstáculos en el mismo corredor tienen una profundidad creciente, lo que significa que para destruir el segundo obstáculo colocado en el corredor se necesita ~5~ veces más energía que el habitual para destruir el tercer obstáculo colocado en el corredor requiere ~25~ veces más energía que el habitual, y destruir el cuarto obstáculo colocado en el mismo corredor requiere ~125~ veces más energía que el habitual. Independientemente de la dirección del corredor MegaBit para eliminar los obstáculos, la energía consumida es la misma, dependiendo solo del orden en que se colocaron los obstáculos de GigaBit. MegaBit no eliminará los obstáculos en todos los pasillos, sino los necesarios para acceder a cada muñeca. MegaBit quiere dejar que el otro ninja entrene, así que lo hace para ayudar a minimizar los obstáculos de tipo ~E~ y luego usar un número mínimo de unidades de energía. Para los corredores en los que hay obstáculos de tipo ~E~, ~E~ consumirá energía solo para los obstáculos de tipo ~A, B, C~ y ~D~. Inicialmente, MegaBit está al lado de la muñeca ~1~.

Tarea

1) Especifica cuántas de las ~n~ muñecas pueden alcanzar a MegaBit antes de solicitar la ayuda de los otros ninjas.

2) Especifique para liberar los corredores para solicitar ayuda externa para llegar a todas las ~n~ muñecas y cuántos obstáculos de tipo ~E~ hay totalmente en estos corredores.

3) Especifique el número mínimo de unidades de energía utilizadas.

Entrada

La entrada contiene en la primera línea un número natural ~v~ que solo puede tener valores ~1~, ~2~ o ~3~ que representan el requisito a resolver. En la segunda línea los números naturales ~n~ y ~m~ separados por un espacio, y las siguientes ~m~ líneas para cada corredor, dos números naturales separados por un espacio que representa las dos muñecas entre las cuales circulan en el respectivo corredor, seguido de un espacio y cuatro letras correspondientes a los cuatro tipos de obstáculos en el orden en que GigaBit los colocó en el corredor. No hay espacio entre las cuatro letras.

Salida

Si el valor de ~v~ es ~1~, su salida contendrá en la primera línea solo el número de muñecas que MegaBit puede alcanzar antes de solicitar la ayuda de los otros ninjas.

Si el valor de ~v~ es ~2~, entonces su salida contendrá el número de corredores en la primera línea que no puede liberar por sí solo, y en la segunda línea el número total de obstáculos tipo ~E~ en estos corredores.

Si el valor de ~v~ es ~3~, su salida contendrá solo el número mínimo de unidades de energía utilizadas en la primera línea.

Restricciones y aclaraciones.

• ~1 \le N, M \le 31200~;

• Para la correcta resolución del primer requisito, se otorgan ~20~ puntos;

• Para la correcta resolución del segundo requisito, se otorgan ~30~ puntos;

• Para la correcta resolución del tercer requisito, se otorgan ~50~ puntos.

Ejemplo de Entrada #1

1
9 15
1 2 CBAA 
1 5 ABAA 
2 6 CBEA 
2 7 ACBA 
2 5 CBEA 
3 4 ABAA 
3 7 AECE 
3 8 CBAC 
3 9 ECEE 
4 8 DBAD 
4 9 ECEB 
5 6 CBAD 
5 7 BAAD 
6 7 CBAA 
7 8 ECEB

Ejemplo de Salida #1

5

Explicación:

MegaBit puede alcanzar los nodos ~1~, ~2~, ~5~, ~6~, ~7~

liberando los corredores ~(1,2)~, ~(1,5)~, ~(2,7)~ y ~(6,7)~

Ejemplo de Entrada #2

2
9 15
1 2 CBAA 
1 5 ABAA 
2 6 CBEA 
2 7 ACBA 
2 5 CBEA 
3 4 ABAA 
3 7 AECE 
3 8 CBAC 
3 9 ECEE 
4 8 DBAD 
4 9 ECEB 
5 6 CBAD 
5 7 BAAD 
6 7 CBAA 
7 8 ECEB

Ejemplo de Salida #2

2
4

Explicación:

MegaBit tiene que pedir ayuda para liberar ~2~ corredores para llegar a las ~9~ muñecas.

MegaBit necesita ayuda para liberar los corredores ~(3,7)~ y ~(4,9)~. En cada uno de estos ~2~ corredores, hay ~2~ obstáculos de tipo ~E~, por lo que hay un total de 4 obstáculos de tipo ~E~.

Ejemplo de Entrada #3

3
9 15
1 2 CBAA 
1 5 ABAA 
2 6 CBEA 
2 7 ACBA 
2 5 CBEA 
3 4 ABAA 
3 7 AECE 
3 8 CBAC 
3 9 ECEE 
4 8 DBAD 
4 9 ECEB 
5 6 CBAD 
5 7 BAAD 
6 7 CBAA 
7 8 ECEB

Ejemplo de Salida #3

1593

Explicación:

MegaBit consumirá al menos ~1593~ unidades de energía de la siguiente manera:

~163~ para el corredor ~(1,2)~

~161~ para corredor ~(1,5)~

~191~ para el corredor ~(2,7)~

~161~ para el corredor ~(3,4)~

~76~ para el corredor ~(3,7)~

~413~ para corredor ~(3,8)~

~265~ para el corredor ~(4,9)~

~163~ para el corredor ~(6,7)~

Para el corredor ~(4,9)~ los obstáculos son ~ECEB~,

Así que MegaBit consumirá ~0 + 3 * 5 + 0 * 25 + 2 * 125 = 265~ unidades de energía