L. FYC's luv letter
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

FYC is a fucking cute boy who wants to write a beautiful love letter to the girl he likes. FYC knows a kind of character magic, and to show his sincerity, he first writes a love letter and then wishes to polish it with his own magic.

​ A love letter is a string, and a beautiful love letter must be a palindrome. FYC hopes that throughout the polishing process, his love letters will always be beautiful, that is, before using magic, during the process of being modified by magic, and after being modified by magic, love letters are always palindrome strings. ​ The magic of FYC is carried out on the magic dictionary. There are $$$n$$$ pages in the dictionary, and each page has a string. If the current love letter of FYC is the same as a certain substring of a certain page, then the love letter can be combined with the substring, and then modified by magic. FYC has the following three kinds of magic:

1. If the substring of the current string has two identical characters outside the two ends, you can spend $$$a_{ij}$$$ costs to add these two identical characters to your love letter.

2. You can spend $$$b_{ij}$$$ costs to delete the characters on both ends of the current love letter, but your love letter cannot be empty.

3. If in a certain position in the entire magic dictionary, there exists a substring that is the same as the substring you currently hold, you can spend $$$|i-j|$$$ costs to jump to the position of another substring, $$$i$$$ and $$$j$$$ are the two page numbers where the string is located. However, the distance of the page number between the target string and the current string cannot exceed $$$k$$$.

FYC has done some operations, but he doesn't know what to do next, and now he wants to ask for your help. That is, the love letter has now been placed on a certain substring on a certain page of the magic dictionary, and now it is hoped that you will use magic to transform the love letter into what he wants, and take it off a certain page . Please tell him what is the minimum cost he needs to spend.

Input

The first line $$$n$$$ and $$$k$$$ indicate a total of $$$n$$$ strings and the range limit of operation $$$3$$$;

The next $$$3n$$$ lines have the following format:

On the first line there is a string representing what the string on page $$$i$$$ of the dictionary looks like. The length of the $$$i^{th}$$$ string is $$$m_i$$$.

The second line contains $$$26$$$ integer, indicating the cost of adding the two identical corresponding character $$$(a-z)$$$ to the current page at the $$$operation 1$$$.

The third line has $$$26$$$ numbers, which represent the cost of deleting $$$(a-z)$$$ the two identical corresponding character in the current page $$$operation 2$$$.

A number on the next line represents the page number of the string where the starting string is located, and a string of characters represents the starting string;

The next line is a number indicating which page FYC wants to get the target string from, and a number indicating which page FYC wants to get the target string in the end;

It is guaranted that all given letters are lower case letters.

$$$1 \le n \le 100000$$$

$$$1 \le m_i \le 1000000$$$

$$$\sum m \le 1000000$$$

$$$k \le n$$$

Output

A line that represents the minimum mana cost. If FYC can't get the love letter he wants, output -1;

Example
Input
2 1
ababa
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ababa
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 a
2 bab
Output
2