F. Isn't it a hard problem?
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

People think that $$$\textit{Somar}$$$ likes palindrome strings, but actually, palindrome strings mean to $$$\textit{Somar}$$$ more than his own life. That's why he always searches for them around the world.

The problem is that a palindrome string is a rare element in nature. Therefore, to obtain a palindrome string, you need to extract it from a normal string (which may or may not be a palindrome) through a difficult process. Of course, $$$\textit{Somar}$$$ is busy and needs your help to extract palindrome strings.

You will be given an array $$$w$$$ consisting of $$$n$$$ strings, each string associated with a score $$$s_i$$$.

You can perform the following operation at most $$$k$$$ times:

  • Change any letter in any string to any other letter.

Your goal is to find the maximum possible score of a beautiful subarray in $$$w$$$, if you can perform the previous operation no more than $$$k$$$ times.

  • We call a string array $$$a$$$ a subarray of $$$w$$$ if it can be obtained by removing any number of strings (possibly zero) from the beginning and end of $$$w$$$. Note that $$$a$$$ could be an empty array.
  • We call a string array $$$a$$$ beautiful if each string in $$$a$$$ is a palindrome string.
  • The score of a string array $$$a$$$ is defined as the sum of the scores of each string in $$$a$$$.
  • A palindrome string is a string that remains the same when read from both ends. For example, the strings "z", "aaa", "aba", and "abccba" are palindromes, but the strings "icpc" and "ab" are not.
Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The descriptions of the test cases follow.

For each test case, the first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 10^5, 0 \le k \le 10^9)$$$.

The next $$$n$$$ lines each contain a string $$$w_i$$$ $$$(1 \le |w_i| \le 5\times 10^5)$$$.

The next line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ $$$(-10^9 \le s_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$|w_i|$$$ over all test cases does not exceed $$$5\times 10^5$$$.

Output

For each test case, print one integer: the maximum possible score of a beautiful subarray in $$$w$$$, if you can perform the allowed operation no more than $$$k$$$ times.

Example
Input
3
6 7
you
still
dont
know
me
yet
3 12 -1 -2 9 2
3 12
codeforces
codeblocks
wronganswer
-2 -1 -1
3 2
fftee
depee
treee
3 4 5
Output
18
0
5
Note

in the first test case: change the second string to stits. change the third string to toot. change the fourth string to kook. change the fifth string to ee. so the answer will be: 12-1-2+9 = 18.