Chef Neel was exchanging some important text with his friend Aksy over the phone. Aksy sends him the secret code to open the treasure of the beautiful valley of Srinagar. However due to disturbances in the medium , the original msg got distorted. Some new characters got added and some were removed while a few got replaced by some other characters. The good thing is that the treasure can be opened with any anagram of the original msg. The majestic master mkm who is blessed with some extraordinary superpowers, knows all the anagrams of the original string. But he charges some cost for every operation he does on the string to convert it into any of the anagrams of the original one.
The operation the majestic master mkm can do on the distorted string along with the cost are given below :
- Delete: Delete a character at any position in string. Operation cost is A.
- Insert: Insert a character at any position in string. Operation cost is B.
- Replace: Replace a character at any position by some other character. Operation cost is C.
Because Chef is running short of money as he spent a lot on his girlfriend's birthday earlier this month , help chef to find out the minimum cost to convert the distorted string into some anagram of the original string.
First line of input is an integer T, total number of test cases.
For each test case there are three lines of input:
- First line contains a string D,the distorted message.
- Second line contains a string U,the original message.
- Third line contains three space separated integers A, B and C, denoting the costs of the operations.
For each test case output in a new line the minimum cost to transform the distorted string into some anagram of the original string.
- 1 ≤ T ≤ 5000
- 1 ≤ |D|,|U| ≤ 20000
- 1 ≤ A,B,C ≤ 1000
Input: 3 cca ccba 0 1 2 bbca acac 3 3 2 baaaba aabaab 2 3 5 Output: 1 4 0
- In the first case we need to add one character 'b'. The cost comes out to be 1
- In the second case we can delete two 'b'and add one 'c' and one 'a'. The cost comes out to be 12. We can also convert using 1 add, 1 delete and 1 replace operation. The cost comes out to be 8.Or we can replace two elements to get anagram of original string. This costs 4. So the minimum cost is 4.
- In the third case , the string is already an anagram of the original one.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions