405887: GYM102152 E Building Strings

You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters. This string can be used to build other strings. The cost of each letter in $$$s$$$ is given by another string $$$c$$$ of length $$$n$$$ consisting of digits, such that the cost of using the letter $$$s_i$$$ is $$$c_i$$$ coins.

Also, you are given another string $$$p$$$ of length $$$m$$$ consisting of unique lowercase English letters. Your task is to find the minimum cost to build string $$$p$$$ by using the letters of $$$s$$$. Can you?

The first line contains an integer $$$T$$$ ($$$1 \le T \le 500$$$) specifying the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^3,\,1 \le m \le 26$$$), in which $$$n$$$ is the length of strings $$$s$$$ and $$$c$$$, and $$$m$$$ is the length of string $$$p$$$.

Then $$$3$$$ lines follow, each line contains a string, giving the string $$$s$$$, $$$c$$$, and $$$p$$$, respectively. Both strings $$$s$$$ and $$$p$$$ contains only lowercase English letters, while string $$$c$$$ contains only digits. Also, string $$$p$$$ is consisting of unique letters.

For each test case, print a single line containing the minimum cost of building the string $$$p$$$ by using the letters of string $$$s$$$. If string $$$p$$$ cannot be built using string $$$s$$$, print $$$-1$$$.

3
4 2
abcd
1234
ac
4 4
abcd
1234
abec
5 3
abcba
24513
acb

4
-1
8

In the first test case, you have to use the $$$1^{st}$$$ and $$$3^{rd}$$$ letters of string $$$s$$$ to build string $$$p$$$. So, the total cost is $$$1 + 3 = 4$$$.

In the second test case, you cannot build string $$$p$$$ using $$$s$$$ because the letter 'e' from $$$p$$$ does not exist in $$$s$$$. So, the answer is $$$-1$$$.

In the third test case, the optimal way is to use the $$$1^{st}$$$, $$$3^{rd}$$$, and $$$4^{th}$$$ letters of string $$$s$$$ to build $$$p$$$. So, the total cost is $$$2 + 5 + 1 = 8$$$.