{"problem":{"name":"E. Building Strings","description":{"content":"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 lengt","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10215E"},"statements":[{"statement_type":"Markdown","content":"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.\n\nAlso, 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?\n\nThe first line contains an integer $T$ ($1 <= T <= 500$) specifying the number of test cases.\n\nThe first line of each test case contains two integers $n$ and $m$ ($1 <= n <= 10^3, thin 1 <= m <= 26$), in which $n$ is the length of strings $s$ and $c$, and $m$ is the length of string $p$.\n\nThen $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.\n\nFor 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$.\n\nIn the first test case, you have to use the $1^(s t)$ and $3^(r d)$ letters of string $s$ to build string $p$. So, the total cost is $1 + 3 = 4$.\n\nIn 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$.\n\nIn the third test case, the optimal way is to use the $1^(s t)$, $3^(r d)$, and $4^(t h)$ letters of string $s$ to build $p$. So, the total cost is $2 + 5 + 1 = 8$.\n\n## Input\n\nThe first line contains an integer $T$ ($1 <= T <= 500$) specifying the number of test cases.The first line of each test case contains two integers $n$ and $m$ ($1 <= n <= 10^3, thin 1 <= m <= 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.\n\n## Output\n\nFor 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$.\n\n[samples]\n\n## Note\n\nIn the first test case, you have to use the $1^(s t)$ and $3^(r d)$ 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^(s t)$, $3^(r d)$, and $4^(t h)$ letters of string $s$ to build $p$. So, the total cost is $2 + 5 + 1 = 8$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, m \\in \\mathbb{Z} $ denote the lengths of strings $ s $, $ c $ and $ p $, respectively.  \n- Let $ s = (s_1, s_2, \\dots, s_n) $ be a string of lowercase English letters.  \n- Let $ c = (c_1, c_2, \\dots, c_n) $ be a string of digits, where $ c_i \\in \\{0,1,\\dots,9\\} $ represents the cost of letter $ s_i $.  \n- Let $ p = (p_1, p_2, \\dots, p_m) $ be a string of $ m $ unique lowercase English letters.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 500 $  \n2. $ 1 \\le n \\le 10^3 $, $ 1 \\le m \\le 26 $  \n3. $ s_i \\in \\{a,b,\\dots,z\\} $, $ c_i \\in \\{0,1,\\dots,9\\} $, $ p_j \\in \\{a,b,\\dots,z\\} $  \n4. All characters in $ p $ are distinct.  \n\n**Objective**  \nFor each test case, compute the minimum total cost to construct $ p $ using letters from $ s $, where:  \n- Each occurrence of a letter $ p_j $ in $ s $ can be used at cost $ c_i $ if $ s_i = p_j $.  \n- Each letter in $ p $ must be matched to exactly one occurrence in $ s $.  \n- If any letter in $ p $ does not appear in $ s $, return $ -1 $.  \n\nDefine for each letter $ \\ell \\in p $:  \n$$\n\\text{cost}(\\ell) = \\min \\{ c_i \\mid s_i = \\ell \\}\n$$  \nIf $ \\exists \\ell \\in p $ such that $ \\ell \\notin \\{s_1, \\dots, s_n\\} $, then output $ -1 $.  \nOtherwise, output:  \n$$\n\\sum_{\\ell \\in p} \\text{cost}(\\ell)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10215E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}