El asesino ABCD#9747
Oscar es un gran aficionado a las películas de crímenes. Admira mucho lo creativos que pueden llegar a ser algunos villanos, y ahora quiere mostrar algo de creatividad propia. Por desgracia, a Oscar le falta experiencia y no se le ocurre un truco original, así que decide inspirarse en uno clásico.
A Oscar siempre le ha fascinado la escena en la que los criminales recortan letras de los periódicos y las juntan para formar una nota de rescate. Sin embargo, no quiere ser un simple imitador. En su lugar, inventa su propia variante de este truco: en vez de componer el mensaje letra por letra (lo que le resulta demasiado aburrido y lento), decide recortar palabras enteras.
Oscar compra varios periódicos de gran tirada, lo que le proporciona una cantidad de papel prácticamente ilimitada: puede recortar cualquier palabra que aparezca en los periódicos tantas veces como necesite. No obstante, su elección sigue estando limitada al conjunto de palabras realmente impresas en los periódicos — algunas palabras pueden simplemente no aparecer nunca.
Para simplificar las cosas, Oscar decide eliminar de la nota de rescate todos los signos de puntuación y los espacios, y no distinguir entre mayúsculas y minúsculas. También permite que las palabras recortadas se solapen, siempre que las partes solapadas sean idénticas.
Ahora Oscar quiere saber el número mínimo de palabras que necesita recortar de los periódicos para componer la nota de rescate.
La primera línea contiene un entero l~(1 \le l \le 3 \cdot 10^5) — el número de palabras encontradas en los periódicos.
La segunda línea contiene el texto de la nota de rescate — una cadena no vacía formada únicamente por letras inglesas minúsculas. Su longitud no supera 3 \cdot 10^5.
Cada una de las siguientes líneas contiene una palabra que aparece en los periódicos, formada por letras inglesas minúsculas. Ninguna palabra está vacía ni es más larga que la nota de rescate. La longitud total de todas las palabras no supera 3 \cdot 10^5. La misma palabra puede aparecer varias veces en la entrada.
Imprima un entero — el número mínimo de palabras que Oscar tiene que recortar de los periódicos para componer la nota de rescate. Cada palabra se cuenta tantas veces como realmente se recorta. Si la nota de rescate no se puede componer con las palabras dadas, imprima .
Ejemplo 1
Ejemplo 2
Ejemplo 3