#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int maxn = 522, sigma = 26;
int a[maxn];
int to[maxn][sigma];
int link[maxn], cost[maxn];
int sz = 1;
void add_str(string s, int n)
{
int v = 0;
for(auto c: s)
{
c -= 'a';
if(!to[v][c])
to[v][c] = sz++;
v = to[v][c];
}
cost[v] += a[n];
}
void push_links()
{
int que[sz];
int st = 0, fi = 1;
que[0] = 0;
while(st < fi)
{
int v = que[st++];
int u = link[v];
cost[v] += cost[u];
for(int c = 0; c < sigma; c++)
{
if(to[v][c])
{
link[to[v][c]] = v ? to[u][c] : 0;
que[fi++] = to[v][c];
}
else
{
to[v][c] = to[u][c];
}
}
}
}
signed main()
{
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int n, l;
cin >> n >> l;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
add_str(s, i);
}
push_links();
const int logn = 50;
int best[logn][sz][sz];
memset(best, -1, sizeof(best));
for(int i = 0; i < sz; i++)
for(int c = 0; c < sigma; c++)
best[0][i][to[i][c]] = cost[to[i][c]];
for(int z = 1; z < logn; z++)
for(int k = 0; k < sz; k++)
for(int i = 0; i < sz; i++)
for(int j = 0; j < sz; j++)
if(best[z - 1][i][k] != -1 && best[z - 1][k][j] != -1)
best[z][i][j] = max(best[z][i][j], best[z - 1][i][k] + best[z - 1][k][j]);
int ans[sz][sz];
memset(ans, -1, sizeof(ans));
for(int i = 0; i < sz; i++)
ans[i][i] = 0;
for(int z = 0; z < logn; z++)
{
if((l >> z) & 1)
{
int tmp[sz][sz];
memset(tmp, -1, sizeof(tmp));
for(int k = 0; k < sz; k++)
for(int i = 0; i < sz; i++)
for(int j = 0; j < sz; j++)
if(ans[i][k] != -1 && best[z][k][j] != -1)
tmp[i][j] = max(tmp[i][j], ans[i][k] + best[z][k][j]);
memcpy(ans, tmp, sizeof(ans));
}
}
int out = 0;
for(int i = 0; i < sz; i++)
out = max(out, ans[0][i]);
cout << out << "\n";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBpbnQgaW50NjRfdAoKY29uc3QgaW50IG1heG4gPSA1MjIsIHNpZ21hID0gMjY7CmludCBhW21heG5dOwoKaW50IHRvW21heG5dW3NpZ21hXTsKaW50IGxpbmtbbWF4bl0sIGNvc3RbbWF4bl07CmludCBzeiA9IDE7CnZvaWQgYWRkX3N0cihzdHJpbmcgcywgaW50IG4pCnsKICAgIGludCB2ID0gMDsKICAgIGZvcihhdXRvIGM6IHMpCiAgICB7CiAgICAgICAgYyAtPSAnYSc7CiAgICAgICAgaWYoIXRvW3ZdW2NdKQogICAgICAgICAgICB0b1t2XVtjXSA9IHN6Kys7CiAgICAgICAgdiA9IHRvW3ZdW2NdOwogICAgfQogICAgY29zdFt2XSArPSBhW25dOwp9Cgp2b2lkIHB1c2hfbGlua3MoKQp7CiAgICBpbnQgcXVlW3N6XTsKICAgIGludCBzdCA9IDAsIGZpID0gMTsKICAgIHF1ZVswXSA9IDA7CiAgICB3aGlsZShzdCA8IGZpKQogICAgewogICAgICAgIGludCB2ID0gcXVlW3N0KytdOwogICAgICAgIGludCB1ID0gbGlua1t2XTsKICAgICAgICBjb3N0W3ZdICs9IGNvc3RbdV07CiAgICAgICAgZm9yKGludCBjID0gMDsgYyA8IHNpZ21hOyBjKyspCiAgICAgICAgewogICAgICAgICAgICBpZih0b1t2XVtjXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGlua1t0b1t2XVtjXV0gPSB2ID8gdG9bdV1bY10gOiAwOwogICAgICAgICAgICAgICAgcXVlW2ZpKytdID0gdG9bdl1bY107CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0b1t2XVtjXSA9IHRvW3VdW2NdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgpzaWduZWQgbWFpbigpCnsKICAgIC8vZnJlb3BlbigiaW5wdXQudHh0IiwgInIiLCBzdGRpbik7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBpbnQgbiwgbDsKICAgIGNpbiA+PiBuID4+IGw7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgIGNpbiA+PiBhW2ldOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgIHsKICAgICAgICBzdHJpbmcgczsKICAgICAgICBjaW4gPj4gczsKICAgICAgICBhZGRfc3RyKHMsIGkpOwogICAgfQogICAgcHVzaF9saW5rcygpOwogICAgY29uc3QgaW50IGxvZ24gPSA1MDsKICAgIGludCBiZXN0W2xvZ25dW3N6XVtzel07CiAgICBtZW1zZXQoYmVzdCwgLTEsIHNpemVvZihiZXN0KSk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgc3o7IGkrKykKICAgICAgICBmb3IoaW50IGMgPSAwOyBjIDwgc2lnbWE7IGMrKykKICAgICAgICAgICAgYmVzdFswXVtpXVt0b1tpXVtjXV0gPSBjb3N0W3RvW2ldW2NdXTsKICAgIGZvcihpbnQgeiA9IDE7IHogPCBsb2duOyB6KyspCiAgICAgICAgZm9yKGludCBrID0gMDsgayA8IHN6OyBrKyspCiAgICAgICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzejsgaSsrKQogICAgICAgICAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IHN6OyBqKyspCiAgICAgICAgICAgICAgICAgICAgaWYoYmVzdFt6IC0gMV1baV1ba10gIT0gLTEgJiYgYmVzdFt6IC0gMV1ba11bal0gIT0gLTEpCiAgICAgICAgICAgICAgICAgICAgICAgIGJlc3Rbel1baV1bal0gPSBtYXgoYmVzdFt6XVtpXVtqXSwgYmVzdFt6IC0gMV1baV1ba10gKyBiZXN0W3ogLSAxXVtrXVtqXSk7CiAgICBpbnQgYW5zW3N6XVtzel07CiAgICBtZW1zZXQoYW5zLCAtMSwgc2l6ZW9mKGFucykpOwogICAgZm9yKGludCBpID0gMDsgaSA8IHN6OyBpKyspCiAgICAgICAgYW5zW2ldW2ldID0gMDsKICAgIGZvcihpbnQgeiA9IDA7IHogPCBsb2duOyB6KyspCiAgICB7CiAgICAgICAgaWYoKGwgPj4geikgJiAxKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHRtcFtzel1bc3pdOwogICAgICAgICAgICBtZW1zZXQodG1wLCAtMSwgc2l6ZW9mKHRtcCkpOwogICAgICAgICAgICBmb3IoaW50IGsgPSAwOyBrIDwgc3o7IGsrKykKICAgICAgICAgICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzejsgaSsrKQogICAgICAgICAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7IGogPCBzejsgaisrKQogICAgICAgICAgICAgICAgICAgICAgICBpZihhbnNbaV1ba10gIT0gLTEgJiYgYmVzdFt6XVtrXVtqXSAhPSAtMSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRtcFtpXVtqXSA9IG1heCh0bXBbaV1bal0sIGFuc1tpXVtrXSArIGJlc3Rbel1ba11bal0pOwogICAgICAgICAgICBtZW1jcHkoYW5zLCB0bXAsIHNpemVvZihhbnMpKTsKICAgICAgICB9CiAgICB9CiAgICBpbnQgb3V0ID0gMDsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzejsgaSsrKQogICAgICAgIG91dCA9IG1heChvdXQsIGFuc1swXVtpXSk7CiAgICBjb3V0IDw8IG91dCA8PCAiXG4iOwoJcmV0dXJuIDA7Cn0=
MiA5ODUxMAo5OSAxMDAKYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJiYmJ5CmFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYXo=
2 98510
99 100
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbby
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz