Cumplidos#2602

Cumplidos

1 segundo
128 megabytes

Anya quiere escribirle a Vanya un mensaje que le levante el ánimo lo máximo posible. Vanya conoce cumplidos. Cada cumplido es una cadena no vacía de letras latinas minúsculas. Algunos cumplidos pueden escribirse de la misma forma: son cumplidos distintos que resultan estar escritos igual.

Al principio, el ánimo de Vanya es . Cada vez que el -ésimo cumplido aparece en el mensaje como una subcadena contigua, el ánimo de Vanya aumenta en a_i. Las apariciones pueden solaparse y cada una de ellas se cuenta por separado. Por ejemplo, en el mensaje la cadena aparece dos veces y la cadena aparece una vez.

El mensaje puede contener a lo sumo caracteres. Halle el valor máximo que puede alcanzar el ánimo de Vanya después de leer el mensaje.

Entrada

La primera línea contiene dos enteros y l~(1 \le n \le 200, 1 \le l \le 10^{14}) — la cantidad de cumplidos y la longitud máxima permitida del mensaje.

La segunda línea contiene enteros a_1, a_2, \ldots, a_n~(1 \le a_i \le 100). El número a_i es la cantidad en que aumenta el ánimo de Vanya con cada aparición del -ésimo cumplido.

Cada una de las siguientes líneas contiene un cumplido: la -ésima de ellas contiene una cadena no vacía s_i de letras latinas minúsculas. La longitud total de todas las cadenas s_i no supera .

Salida

Imprima un entero — el valor máximo posible del ánimo de Vanya.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Nota

En el primer ejemplo sirve el mensaje : cada cumplido aparece en él exactamente una vez y el ánimo es 3 + 2 + 1 = 6.

En el segundo ejemplo sirve el mensaje artart: el cumplido aparece en él dos veces y el ánimo es 8 + 8 = 16.