402860: GYM100923 D Por Costel and the Censorship Committee

Por Costel the pig is ready to change his status on Vasebook. But wait!! What's this?

It seems that the evil Mark Suckerberg was not truthful about his opinions of free speech on Vasebook. He has gathered up a censorship committee in order to censor the pig's message. Suckerberg is sick of seeing words, such as "cob", "pig", "yummy" and so on, all over Vasebook. He has come up with an entire list of these outrageous words. The committee will need to select a subset of letters from the message and replace them with '*'. After this process, none of the words in Suckerberg's list should appear as a substring in Por Costel's message.

You are part of the censorship committee, but, secretly, you are also a Por Costel fan. You know that each letter of the message has a certain importance in its context(the letter on position i has importance ). You don't want Por Costel's message to lose its significance, but neither do you want to lose your job at VaseBook. Censor the message such that sum of the importance values of censored letters (letters replaced with '*') is minimum.

The first line of the file cenzura.in contains an integer (), the number of tests.

Each of the tests has the following format:

First line contains an integer (), the length of Por Costel's message.

The second line contains a string of characters, the message itself.

The third line will be a sequence of integer numbers () separated by single spaces. signifies the importance of the -th letter of the message.

The fourth line will contain an integer (), the number of words in Suckerberg's list

The next lines will contain the aforementioned words. The length of each word is at most

The total number of appearances of Suckerberg's words in Por Costel's message will not exceed .

Por Costel's message and Suckerberg's words are all comprised of lower case letters of the English alphabet(a to z).

The file cenzura.out should contain lines.

Each of these should contain a single number, the minimum sum of importance of censored letters such that the message is censored correctly on that particular test case.

1
23
cresteporciisefacepateu
1 2 3 4 5 6 7 8 9 8 9 9 2 3 2 1 4 7 8 6 5 6 7
3
porci
rcii
pateu

13