Anya vuole scrivere a Vanya un messaggio che gli sollevi l'umore il più possibile. Vanya conosce complimenti. Ogni complimento è una stringa non vuota di lettere latine minuscole. Alcuni complimenti possono essere scritti allo stesso modo: sono complimenti diversi che risultano scritti in modo identico.
Inizialmente, l'umore di Vanya è . Ogni volta che l'-esimo complimento compare nel messaggio come sottostringa contigua, l'umore di Vanya aumenta di a_i. Le occorrenze possono sovrapporsi, e ciascuna di esse viene contata separatamente. Ad esempio, nel messaggio la stringa compare due volte, e la stringa compare una volta.
Il messaggio può contenere al massimo caratteri. Trova il valore massimo che l'umore di Vanya può raggiungere dopo aver letto il messaggio.
La prima riga contiene due interi e l~(1 \le n \le 200, 1 \le l \le 10^{14}) — il numero di complimenti e la lunghezza massima consentita del messaggio.
La seconda riga contiene interi a_1, a_2, \ldots, a_n~(1 \le a_i \le 100). Il numero a_i è la quantità di cui aumenta l'umore di Vanya ad ogni occorrenza dell'-esimo complimento.
Ciascuna delle successive righe contiene un complimento: la -esima di esse contiene una stringa non vuota s_i di lettere latine minuscole. La lunghezza totale di tutte le stringhe s_i non supera .
Stampa un intero — il valore massimo possibile dell'umore di Vanya.
Esempio 1
Esempio 2
Nel primo esempio, il messaggio funziona: ogni complimento compare esattamente una volta, e l'umore è pari a 3 + 2 + 1 = 6.
Nel secondo esempio, il messaggio artart funziona: il complimento compare due volte, e l'umore è pari a 8 + 8 = 16.