2019 JUST Programming Contest |
---|
Finished |
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$$$.
Name |
---|