Algorithms
Hard
2977
3238
Minimum Cost to Convert String II
minimum-cost-to-convert-string-ii
"""
You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:

The substrings picked in the operations are source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.
The substrings picked in the operations are source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.
Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert "abcd" to "acbe", do the following operations:
- Change substring source[1..1] from "b" to "c" at a cost of 5.
- Change substring source[2..2] from "c" to "e" at a cost of 1.
- Change substring source[2..2] from "e" to "b" at a cost of 2.
- Change substring source[3..3] from "d" to "e" at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28. 
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
Output: 9
Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations:
- Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
- Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.

Example 3:

Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
Output: -1
Explanation: It is impossible to convert "abcdefgh" to "addddddd".
If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.


Constraints:

1 <= source.length == target.length <= 1000
source, target consist only of lowercase English characters.
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i], changed[i] consist only of lowercase English characters.
original[i] != changed[i]
1 <= cost[i] <= 106
"""
class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        
You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:

The substrings picked in the operations are source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.
The substrings picked in the operations are source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.
Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert "abcd" to "acbe", do the following operations:
- Change substring source[1..1] from "b" to "c" at a cost of 5.
- Change substring source[2..2] from "c" to "e" at a cost of 1.
- Change substring source[2..2] from "e" to "b" at a cost of 2.
- Change substring source[3..3] from "d" to "e" at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28. 
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
Output: 9
Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations:
- Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
- Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.

Example 3:

Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
Output: -1
Explanation: It is impossible to convert "abcdefgh" to "addddddd".
If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.


Constraints:

1 <= source.length == target.length <= 1000
source, target consist only of lowercase English characters.
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i], changed[i] consist only of lowercase English characters.
original[i] != changed[i]
1 <= cost[i] <= 106


Please complete the code below to solve above prblem:
```python
class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "source": "abcd", "target": "acbe", "original": ["a","b","c","c","e","d"], "changed": ["b","c","b","e","b","e"], "cost": [2,5,5,1,2,20] }
assert my_solution.minimumCost(**test_input) == 28

test_input = { "source": "abcdefgh", "target": "acdeeghh", "original": ["bcd","fgh","thh"], "changed": ["cde","thh","ghh"], "cost": [1,3,5] }
assert my_solution.minimumCost(**test_input) == 9

test_input = { "source": "abcdefgh", "target": "addddddd", "original": ["bcd","defgh"], "changed": ["ddd","ddddd"], "cost": [100,1578] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "a", "target": "b", "original": ["a"], "changed": ["b"], "cost": [1] }
assert my_solution.minimumCost(**test_input) == 1

test_input = { "source": "a", "target": "c", "original": ["a","b","a","a"], "changed": ["b","c","c","c"], "cost": [1,2,10,1] }
assert my_solution.minimumCost(**test_input) == 1

test_input = { "source": "a", "target": "d", "original": ["a"], "changed": ["b"], "cost": [1] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ajhpd", "target": "djjdc", "original": ["hpd","iyk","qzd","hpi","aic","znh","cea","fug","wir","kwu","yjo","rzi","a","n","f","q","u","w","x","i","x","s","o","u"], "changed": ["iyk","qzd","hpi","aic","znh","cea","fug","wir","kwu","yjo","rzi","jdc","n","f","q","u","w","x","i","x","s","o","u","d"], "cost": [80257,95140,96349,89449,81714,5859,96734,96109,41211,99975,57611,32644,82896,22164,99889,98061,95403,90922,64031,94558,58418,99717,96588,88286] }
assert my_solution.minimumCost(**test_input) == 1264348

test_input = { "source": "bzshh", "target": "mlosr", "original": ["shh","wbs","hup","sab","csp","tel","mhq","ezp","eap","fqb","iea","cej","b","v","g","e","d","x","q","v","g","x","u","m","u","q","z","q","n","p"], "changed": ["wbs","hup","sab","csp","tel","mhq","ezp","eap","fqb","iea","cej","osr","v","g","e","d","x","q","v","g","x","u","m","u","q","m","q","n","p","l"], "cost": [69565,82190,75322,85502,89675,98424,86521,85852,32285,99465,82356,97775,30173,88276,82158,40971,75361,65284,89814,68219,44777,95082,99781,99072,74513,49667,99719,93132,99203,54171] }
assert my_solution.minimumCost(**test_input) == 1589277

test_input = { "source": "fjybg", "target": "apyyt", "original": ["bg","xr","cc","ip","vq","po","ym","rh","vw","lf","lo","ee","qv","yr","f","w","i","u","g","a","e","f","s","r","p","j","o","g","i","u"], "changed": ["xr","cc","ip","vq","po","ym","rh","vw","lf","lo","ee","qv","yr","yt","w","i","u","g","a","e","f","s","r","p","a","o","g","i","u","p"], "cost": [97733,90086,87125,85361,75644,46301,21616,79538,52507,95884,79353,61127,58665,96031,95035,12116,41158,91096,47819,88522,25493,80186,66981,87597,56691,86820,89031,99954,41271,39699] }
assert my_solution.minimumCost(**test_input) == 1628332

test_input = { "source": "htkdz", "target": "oaqaw", "original": ["kdz","yyv","cde","oks","fzu","hkm","dmb","arh","lix","eij","ksv","t","u","f","w","b","u","v","h","o","b","o","p","z","h","w","t","p","x","y"], "changed": ["yyv","cde","oks","fzu","hkm","dmb","arh","lix","eij","ksv","qaw","u","f","w","b","u","v","h","o","b","o","p","z","a","w","t","p","x","y","o"], "cost": [90243,86765,84893,80924,85915,42672,99995,99429,88069,84925,71184,54929,83245,72750,87238,30151,58657,94445,98330,90683,83980,96513,75536,95212,79301,74556,94836,94781,76273,86147] }
assert my_solution.minimumCost(**test_input) == 1278928

test_input = { "source": "iktgh", "target": "srwcg", "original": ["h","e","y","g","q","y","t","n","r","e","i","x","iktg","xwgv","ddrp","saxt","rvdq","moiy","loln","bkgj","jjgi","vatf"], "changed": ["e","y","g","q","y","t","n","r","e","i","x","g","xwgv","ddrp","saxt","rvdq","moiy","loln","bkgj","jjgi","vatf","srwc"], "cost": [70839,75691,55903,82637,97906,86576,92197,74464,86638,61531,80041,52732,96361,39766,74988,59857,69068,89990,74293,82838,37650,26885] }
assert my_solution.minimumCost(**test_input) == 854129

test_input = { "source": "imbin", "target": "dmhjv", "original": ["bin","pwo","fwt","xwi","xal","uqt","lmp","erq","kac","dgv","qgh","rei","nbx","i","u","b","v","c","q","p","f","q","v","t","n","b"], "changed": ["pwo","fwt","xwi","xal","uqt","lmp","erq","kac","dgv","qgh","rei","nbx","hjv","u","b","v","c","q","p","f","q","v","t","n","b","d"], "cost": [47307,30907,64949,35735,84284,83424,69858,92113,51405,69242,97014,91471,78165,92733,79709,99573,78055,20529,85549,90496,60896,75354,50630,49094,41380,46980] }
assert my_solution.minimumCost(**test_input) == 1115296

test_input = { "source": "jegbx", "target": "ezhfc", "original": ["egbx","hrbf","twne","snjd","ysrf","qzqg","rcll","ekvz","inpr","frxs","xcww","unsw","vdug","ycvs","j","v","j","y","n","q","w","a","z","g","b","d"], "changed": ["hrbf","twne","snjd","ysrf","qzqg","rcll","ekvz","inpr","frxs","xcww","unsw","vdug","ycvs","zhfc","v","j","y","n","q","w","a","z","g","b","d","e"], "cost": [50682,89150,91153,85032,97960,96862,81138,86570,77628,45200,44955,70845,99254,80325,91331,95349,84374,94177,53994,94284,79531,92353,60384,100000,93152,19787] }
assert my_solution.minimumCost(**test_input) == 1868790

test_input = { "source": "jpyjj", "target": "jqnfp", "original": ["j","i","q","u","y","w","d","a","h","s","i","y","w","pyj","qng","lrn","nrm","tvn","fei","fpj","qlw","lrb","ufu","kll","nqp"], "changed": ["i","q","u","y","w","d","a","h","s","i","y","w","p","qng","lrn","nrm","tvn","fei","fpj","qlw","lrb","ufu","kll","nqp","qnf"], "cost": [62657,90954,55348,88767,87756,55487,49700,51801,94877,81661,99027,91814,62872,25235,62153,96875,12009,85321,68993,75866,72888,96411,78568,83975,60456] }
assert my_solution.minimumCost(**test_input) == 1131062

test_input = { "source": "nialx", "target": "qvqfl", "original": ["x","r","a","x","c","w","s","a","n","e","q","p","v","k","o","ial","qzu","owr","kyq","ukk","gpq","jdp","dus","eng","btu","cbp"], "changed": ["r","a","x","c","w","s","a","l","e","q","p","v","k","o","q","qzu","owr","kyq","ukk","gpq","jdp","dus","eng","btu","cbp","vqf"], "cost": [64196,95812,96987,40860,41507,99365,99208,53062,44440,65136,95625,86166,61798,84228,92555,97678,97576,19742,92989,98167,68457,82411,39923,81778,87792,7523] }
assert my_solution.minimumCost(**test_input) == 1096682

test_input = { "source": "pagpe", "target": "xacng", "original": ["gpe","owt","wyv","eba","xgp","uny","ibc","usb","mzj","wdo","lyc","eof","oci","p","e","p","u","h","w","i","l"], "changed": ["owt","wyv","eba","xgp","uny","ibc","usb","mzj","wdo","lyc","eof","oci","cng","e","p","u","h","w","i","l","x"], "cost": [56193,92982,90717,67407,91949,77752,88841,43278,51149,43646,99585,41038,84989,57688,64474,96532,77511,37031,90895,62831,87342] }
assert my_solution.minimumCost(**test_input) == 1381668

test_input = { "source": "aaabbebbbhbbbbebaaeh", "target": "hhbebebbahhhehhbbhee", "original": ["a","b","b","b","e","a","h"], "changed": ["b","e","a","h","h","h","e"], "cost": [9,8,5,9,3,7,9] }
assert my_solution.minimumCost(**test_input) == 99

test_input = { "source": "abbbeebebehbbhhhbeab", "target": "aehebehebaeaebbaahhb", "original": ["b","b","e","e","h","h","h","b","e","a"], "changed": ["e","h","b","a","e","b","a","a","h","h"], "cost": [10,2,9,10,7,8,10,10,6,9] }
assert my_solution.minimumCost(**test_input) == 118

test_input = { "source": "abebbeeeahhbahaehaab", "target": "eebhheeahaahbaebaaea", "original": ["a","b","e","a","h","a","e","b"], "changed": ["e","h","a","h","a","b","b","a"], "cost": [6,8,5,10,10,10,10,8] }
assert my_solution.minimumCost(**test_input) == 149

test_input = { "source": "aeaaebhbhehbeehbehea", "target": "babehheaaeebeebahhba", "original": ["a","e","a","e","b","h","b","h","h","e"], "changed": ["b","a","e","h","h","e","a","a","b","b"], "cost": [8,6,3,8,7,9,9,10,10,5] }
assert my_solution.minimumCost(**test_input) == 109

test_input = { "source": "aeehhhaeebhhbeabeeha", "target": "haaeaabeeeheehbaehha", "original": ["a","e","h","a","h","b","e","b"], "changed": ["h","a","a","b","e","e","h","a"], "cost": [7,9,10,7,8,9,8,8] }
assert my_solution.minimumCost(**test_input) == 117

test_input = { "source": "ahhebhhbbhbebaeehbbh", "target": "hbebaeebebhabeehahhb", "original": ["a","h","h","b","b","e","a","e","h","b"], "changed": ["h","b","e","a","e","a","e","h","a","h"], "cost": [4,8,2,8,9,9,9,8,9,6] }
assert my_solution.minimumCost(**test_input) == 116

test_input = { "source": "babhbaaabbabehhhaaea", "target": "aabhhaebehbaehahbahb", "original": ["b","b","a","a","e"], "changed": ["a","h","e","b","h"], "cost": [2,10,8,4,6] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bbaaaebhhbehaaaabbab", "target": "aebahaaabheebbaehbbb", "original": ["b","b","a","e","h","h","a","a","b"], "changed": ["a","e","h","a","a","b","b","e","h"], "cost": [6,8,3,10,10,7,7,9,10] }
assert my_solution.minimumCost(**test_input) == 120

test_input = { "source": "bbabeehehhbhbhbbaabb", "target": "heaabheabehhahhabhhe", "original": ["b","b","b","e","h","e","h","a","a"], "changed": ["h","e","a","b","e","a","b","b","h"], "cost": [7,6,5,9,7,3,10,10,6] }
assert my_solution.minimumCost(**test_input) == 116

test_input = { "source": "bbhbahbbbabhbbbbbhaa", "target": "aheebebehaeheehhbahh", "original": ["b","b","h","b","a","a"], "changed": ["a","h","e","e","b","h"], "cost": [3,5,9,9,5,10] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "beeeaehhbbbaeaeebabh", "target": "ahehaahaaehhabaehbah", "original": ["b","e","e","h","b","a","a"], "changed": ["a","h","a","a","h","h","b"], "cost": [3,5,5,10,1,7,2] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bhabahbhabaahbhahabb", "target": "ehbbhehbbhebaeeheebe", "original": ["a","a","h","b","h","a"], "changed": ["b","h","e","h","b","e"], "cost": [9,10,5,10,10,8] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bhhbaaahheaebehhabeh", "target": "bbhebbeeahahhbeabeba", "original": ["h","b","h","h","e","b","e","a"], "changed": ["b","e","e","a","h","h","b","b"], "cost": [2,8,8,8,10,7,5,7] }
assert my_solution.minimumCost(**test_input) == 131

test_input = { "source": "eaabhhahhhehbabaabae", "target": "bebaehabeehehbehhahh", "original": ["a","a","b","h","h","b","a","e"], "changed": ["e","b","a","e","b","e","h","h"], "cost": [9,9,9,8,6,4,7,10] }
assert my_solution.minimumCost(**test_input) == 158

test_input = { "source": "ebbaebeheabhheeeaeaa", "target": "eehbhebhheeabehbebea", "original": ["b","a","e","e","h","h","a"], "changed": ["e","b","h","b","a","b","e"], "cost": [6,9,10,7,7,7,9] }
assert my_solution.minimumCost(**test_input) == 135

test_input = { "source": "ebbhbheeaeaeeahehahh", "target": "ehhebhahhhhheaaaaahb", "original": ["b","h","e","a","h","e","h"], "changed": ["h","e","h","h","a","a","b"], "cost": [10,7,10,8,10,3,9] }
assert my_solution.minimumCost(**test_input) == 108

test_input = { "source": "eebhehaabeaaaaheheha", "target": "abbbaeaebbhabehbabbb", "original": ["e","h","e","h","a","a","a","h"], "changed": ["b","b","a","e","h","b","e","a"], "cost": [10,10,10,8,9,6,10,10] }
assert my_solution.minimumCost(**test_input) == 139

test_input = { "source": "eeeaehbabbebhhaehaha", "target": "hehbbahabhhababeeeeh", "original": ["e","a","e","h","b","h","h","a","a"], "changed": ["h","b","b","a","h","b","e","e","h"], "cost": [3,9,4,8,9,10,6,10,6] }
assert my_solution.minimumCost(**test_input) == 120

test_input = { "source": "eeehababeeeheebeehah", "target": "hhhabbbbahhehhhbhbab", "original": ["e","h","a","e","h","b","e"], "changed": ["h","a","b","a","e","h","b"], "cost": [7,8,6,10,10,10,9] }
assert my_solution.minimumCost(**test_input) == 143

test_input = { "source": "eehhhbbhebeeehahaaae", "target": "bahaeebhbhhebbbahbhh", "original": ["e","h","b","b","e","e","h","a","h","a"], "changed": ["a","e","e","h","h","b","b","b","a","h"], "cost": [9,9,9,5,3,8,10,2,2,1] }
assert my_solution.minimumCost(**test_input) == 69

test_input = { "source": "ehaaeabaebaehbbhbhbe", "target": "baheeebehhebhbeebbbe", "original": ["e","h","a","a","e","b","b","h"], "changed": ["b","a","h","e","h","h","e","e"], "cost": [8,8,4,10,7,10,10,10] }
assert my_solution.minimumCost(**test_input) == 123

test_input = { "source": "ehaehehbeebaebaeebeb", "target": "eehhebaheaheahhhbeaa", "original": ["h","e","b","e","a","a","e","b","b"], "changed": ["e","h","h","a","e","h","b","e","a"], "cost": [9,8,8,10,10,10,3,10,9] }
assert my_solution.minimumCost(**test_input) == 162

test_input = { "source": "ehbahbbaabhbabahbbhh", "target": "ahbhbehbahaehhaaehhh", "original": ["a","b","h"], "changed": ["h","h","a"], "cost": [9,9,2] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ehbeabbhhebhbahbhbab", "target": "hhbaaebbaaabhhbehhae", "original": ["e","e","b","h","b","a","b"], "changed": ["h","a","a","b","h","h","e"], "cost": [3,8,10,7,5,10,10] }
assert my_solution.minimumCost(**test_input) == 117

test_input = { "source": "hbhheeehehbbhbbehaae", "target": "aebhbheehbbbhabbhebh", "original": ["h","b","h","e","h","e","a","a"], "changed": ["a","e","b","h","e","b","e","b"], "cost": [3,9,8,10,7,8,4,9] }
assert my_solution.minimumCost(**test_input) == 116

test_input = { "source": "hebeebhhhhabaaheabbh", "target": "aeheabaeaaeababeheae", "original": ["h","b","h","a","b","a","h","a","b"], "changed": ["a","h","e","e","a","b","b","h","e"], "cost": [10,6,8,10,10,5,10,10,2] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "hebhhaaaahbehahebaba", "target": "ahhabehbahehhahaehhh", "original": ["h","b","h","a","a","b","e","e"], "changed": ["a","h","b","e","h","e","h","a"], "cost": [6,6,10,9,7,10,10,7] }
assert my_solution.minimumCost(**test_input) == 128

test_input = { "source": "hheahabebabhehahaahe", "target": "eaahbbbaehhhahhhebhe", "original": ["h","h","e","a","a","b","a"], "changed": ["e","a","a","b","h","h","e"], "cost": [3,10,10,8,10,10,10] }
assert my_solution.minimumCost(**test_input) == 140

test_input = { "source": "hhebabehhhhbehaahbhh", "target": "ehhabeahaheaabbehhbe", "original": ["h","e","b","a","b","e","h","h","b"], "changed": ["e","h","a","b","e","a","a","b","h"], "cost": [5,3,9,10,10,6,9,5,10] }
assert my_solution.minimumCost(**test_input) == 127

test_input = { "source": "hhhbbbhhaeabhheaehea", "target": "bebhhaeheahhebbeeahb", "original": ["h","h","b","a","e","a","e","h","e","a"], "changed": ["b","e","h","e","a","h","b","a","h","b"], "cost": [10,6,8,9,6,8,10,5,8,9] }
assert my_solution.minimumCost(**test_input) == 149

test_input = { "source": "anrlqxdnlqcxqdlsceokwgrzkakyqw", "target": "fxynzghpiexaarjuaepxxpaudqipxx", "original": ["a","n","r","l","q","x","d","n","l","q","d","s","k","w","g","z","k","a","k","q"], "changed": ["f","x","y","n","z","g","h","p","i","a","r","u","x","x","p","u","d","q","i","x"], "cost": [78,19,91,27,96,16,95,100,38,99,99,94,82,75,71,100,96,88,78,89] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ayvhtgqvcputvzdksluictwibnvlxx", "target": "pssmcmkjyqniiyiiubwghwldxptuix", "original": ["a","h","t","g","v","c","t","v","z","d","k","s","l","u","i","c","w","b","v","l","x"], "changed": ["p","m","c","m","j","y","i","i","y","i","i","u","b","w","g","h","l","x","t","u","i"], "cost": [82,77,100,95,86,34,77,38,90,31,97,96,77,32,79,87,72,65,100,98,56] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bdkgumfyqsosetnboawzhflcfkhryb", "target": "rqwqiefmafkzmataueoobbfkkxsung", "original": ["b","d","k","g","u","m","y","q","s","o","s","e","t","o","z","h","l","c","f","k","h","r","y","b"], "changed": ["r","q","w","q","i","e","m","a","f","k","z","m","a","u","o","b","f","k","k","x","s","u","n","g"], "cost": [97,97,72,71,84,96,81,53,85,81,85,48,82,47,54,79,63,94,86,66,96,39,80,82] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "dmhqhwozzfespijaadiwceabbxlfgd", "target": "owmyowokqacnhwmaellbhcnoodviac", "original": ["d","m","h","h","z","z","f","s","p","a","d","i","w","c","a","b","x","l","g","d"], "changed": ["o","w","m","o","k","q","a","n","h","e","l","l","b","h","n","o","d","v","a","c"], "cost": [100,55,84,66,97,92,86,86,98,78,71,100,89,74,77,15,59,59,87,86] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "erjbgdadefwtaydgneprfphalkagce", "target": "uzslvcynelwivxyzvhlpoxeulnguvi", "original": ["e","r","j","b","g","d","a","d","f","t","a","y","d","g","e","p","r","f","h","a","k","g","c","e"], "changed": ["u","z","s","l","v","c","y","n","l","i","v","x","y","z","h","l","p","o","e","u","n","u","v","i"], "cost": [36,100,100,98,99,90,98,93,29,80,37,98,82,84,94,97,86,97,73,96,73,92,94,57] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "gsolujonrufkcbigtjvpsgwtcaafjk", "target": "niymoyhbyicgjgcjkqkonhcgyqvhwr", "original": ["g","s","o","j","o","n","u","b","i","g","t","j","v","p","s","g","t","c","a","a","j"], "changed": ["n","i","y","y","h","b","i","g","c","j","k","q","k","o","n","h","g","y","q","v","w"], "cost": [90,91,99,100,97,95,72,56,85,55,96,77,65,21,38,18,54,91,90,99,87] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "haqgciljqjmplyboytkbvzvncembca", "target": "vxjxtxjkvyfvnkfbcfxzwjgmvflduz", "original": ["a","q","g","c","i","l","j","q","j","p","l","b","y","t","b","z","n","c","e","m","c","a"], "changed": ["x","j","x","t","x","j","k","v","y","v","n","f","c","f","z","j","m","v","f","l","u","z"], "cost": [92,99,90,100,86,49,32,98,72,80,87,87,54,56,93,19,94,81,94,98,76,94] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "jdsusoktswdtjkwuawzxxxruaybamd", "target": "ycnwpqplsmumuzggvekrmgtjxxdqwd", "original": ["j","s","u","s","k","t","d","t","j","w","u","a","w","z","x","x","r","u","y","b","m"], "changed": ["y","n","w","p","p","l","u","m","u","g","g","v","e","k","r","g","t","j","x","d","w"], "cost": [40,97,100,79,39,99,59,49,84,95,90,82,87,22,95,90,76,70,66,96,92] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "nwukaumgrqigiynrvteerkcwheiiim", "target": "nkimfbwdsbbbpccfepohlvxapvgxlg", "original": ["w","k","u","m","r","q","g","i","y","n","r","v","t","e","e","r","k","h","e","i","i","i","m"], "changed": ["k","m","b","w","s","b","b","p","c","c","f","e","p","o","h","l","v","p","v","g","x","l","g"], "cost": [63,94,50,93,100,95,99,92,100,28,98,73,80,99,73,77,84,98,64,87,98,60,85] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ovtbwsxlxgefyzlwgslddghfjyvyif", "target": "iobyykxbenmagxgftwubmkrxuvhaxq", "original": ["v","t","s","l","x","g","e","f","y","z","l","g","s","l","d","d","g","h","f","j","y","v","i","f"], "changed": ["o","b","k","b","e","n","m","a","g","x","g","t","w","u","b","m","k","r","x","u","v","h","x","q"], "cost": [95,63,97,83,95,93,81,95,100,83,63,99,97,94,45,100,38,99,18,81,39,73,92,24] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "pkluljeraiornkwyxkowpqlpeemdha", "target": "ckwzwedmdxrkbtgrhrpozwvzwijlri", "original": ["p","l","u","e","a","i","r","n","k","w","y","x","k","o","w","p","q","l","e","e","m"], "changed": ["c","w","z","d","d","x","k","b","t","g","r","h","r","p","o","z","w","v","w","i","j"], "cost": [95,88,96,84,49,86,39,68,64,84,99,96,83,46,95,84,74,64,95,83,67] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "qxzlstqdqpfgswlrztsnnclfnsaajc", "target": "hgjeamofjdcawvbdmwczbctphfupgl", "original": ["q","x","z","l","s","t","q","q","p","g","l","r","z","t","n","n","f","n","s","a","a","j","c"], "changed": ["h","g","j","e","a","m","o","j","d","a","b","d","m","w","z","b","p","h","f","u","p","g","l"], "cost": [91,10,86,97,98,76,100,96,97,59,95,97,67,93,84,64,55,81,97,69,99,81,81] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "sozjzrckkcytmscpjjhbkzsfgofzml", "target": "xjwgnxzbukkqwtocdtjeglsxkjhfsg", "original": ["s","o","z","j","z","r","k","k","s","j","j","h","b","k","z","f","g","f","z","m","l"], "changed": ["x","j","w","g","n","x","b","u","t","d","t","j","e","g","l","x","k","h","f","s","g"], "cost": [92,100,97,100,21,93,47,100,50,44,84,84,50,90,64,83,55,75,73,42,89] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "tahngidhiduqtsaimwqhjfkoyvubhx", "target": "xsglbaliykddukogzcfpchirxnzdlp", "original": ["t","a","h","n","g","i","d","h","i","d","u","q","t","s","a","i","m","w","q","h","f","k","o","v","b","h","x"], "changed": ["x","s","g","l","b","a","l","i","y","k","d","d","u","k","o","g","z","c","f","p","h","i","r","n","d","l","p"], "cost": [26,97,84,85,78,59,98,50,91,100,98,7,96,96,73,82,23,96,59,75,87,79,69,95,41,87,100] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "tqamxbehkpaapskhicnkuyyzkvjxfl", "target": "jlykiobovnobxxwnevqcluhcfmutqu", "original": ["t","q","a","m","x","b","e","h","k","p","p","s","h","i","n","k","u","y","y","z","v","x","l"], "changed": ["j","l","y","k","i","o","b","o","v","n","x","x","n","e","q","c","l","u","h","c","m","t","u"], "cost": [68,73,57,37,99,81,75,93,100,88,50,93,89,96,88,85,70,36,71,77,54,65,94] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ujdbivstmdpnnpnnpggqiwankpoyfw", "target": "grttiosznxkzeapbsjcisymwaetxcl", "original": ["u","d","b","v","t","m","p","n","n","p","n","n","p","g","q","i","w","a","n","p","o","f"], "changed": ["g","t","t","o","z","n","k","z","e","a","p","b","s","c","i","s","y","m","w","e","t","c"], "cost": [100,99,62,99,77,64,56,90,46,94,75,99,87,90,75,83,78,49,100,87,75,20] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "wqomlunjedgsdmdmcwohbxmkeqayxa", "target": "pojjjjzfsrvrhezcdbinplekiwhllb", "original": ["w","o","m","l","u","n","e","d","d","m","d","m","c","o","h","b","x","e","a","y"], "changed": ["p","j","j","j","j","z","s","r","h","e","z","c","d","i","n","p","l","i","h","l"], "cost": [91,91,51,66,89,97,95,89,72,58,98,65,99,63,58,42,89,79,52,42] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "yzflltfyomcnxhwfxcijnsxotwgcuy", "target": "pwdaiitmmlwdyhwpcrhcnncughvchb", "original": ["y","l","l","f","y","o","c","n","x","f","i","j","s","x","o","t","w","g","u","y"], "changed": ["p","a","i","t","m","m","w","d","y","p","h","c","n","c","u","g","h","v","h","b"], "cost": [84,87,90,88,64,80,95,59,96,76,100,93,72,50,97,79,60,90,72,67] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "zchjedhjmkrzqkqnywdgxakcdmsdwg", "target": "cbftcpgezcgjguefrieolevyaadkgb", "original": ["z","c","h","j","e","m","k","r","z","q","k","q","n","y","w","d","x","k","c","m","s","d","w","g"], "changed": ["c","b","f","t","c","z","c","g","j","g","u","e","f","r","i","e","l","v","y","a","d","k","g","b"], "cost": [57,94,71,85,53,96,97,43,93,65,76,93,94,100,81,85,62,100,34,99,95,85,77,68] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "zpxcysgujcbbcgbqqofookukkotwij", "target": "dfxsvtmexhdnfhbdrcdgqlajddteph", "original": ["z","s","g","u","j","c","g","q","o","f","k","u","k","o","w","j"], "changed": ["d","t","m","e","x","f","h","r","c","d","l","a","j","d","e","h"], "cost": [75,28,71,70,92,88,82,82,80,91,97,93,77,14,68,75] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bavusatavvvuubavsauavubtusubsvtsvsbttbvs", "target": "ssauttbvssatusutusbattuttsutabubutuasvuu", "original": ["b","a","v","s","t","a","v","a","v","s","u","u","b","s","v","t","s","b","t","b"], "changed": ["s","s","a","t","b","v","s","u","t","u","b","t","t","a","b","u","b","u","a","v"], "cost": [948,467,690,969,300,877,924,924,791,724,809,652,388,592,772,829,912,679,751,529] }
assert my_solution.minimumCost(**test_input) == 27579

test_input = { "source": "bbvstvuatvbasbbsvsuvvuvvauutttvtsuavsvua", "target": "buvbtutbsbuttbtvabbuvubvbvabsbattutvbvvu", "original": ["b","s","v","u","a","t","v","a","s","u","u","u","t","v","a"], "changed": ["u","b","u","t","b","s","b","t","v","b","v","a","b","a","u"], "cost": [795,956,694,238,665,894,519,867,887,715,845,16,942,429,282] }
assert my_solution.minimumCost(**test_input) == 22249

test_input = { "source": "busbsusauusbbasssutaauttavbbabtbustvubtv", "target": "vuabutaustubbbsbabbusavsttbtubavsabuvvbt", "original": ["b","s","u","s","a","u","s","t","a","u","t","t","v","b","v"], "changed": ["v","u","t","a","u","s","b","b","s","a","v","s","t","t","u"], "cost": [927,992,291,999,989,996,318,196,155,948,375,845,960,949,250] }
assert my_solution.minimumCost(**test_input) == 24291

test_input = { "source": "buuasstsvvvvtsaavstbvubtbstbussbavsvvvbt", "target": "utsabasvssauvuvavvbstbbaauvvvtvtbastatua", "original": ["b","u","u","s","s","v","v","t","b","u","b","s","t","b","u","b","a","v"], "changed": ["u","t","s","b","v","s","a","b","s","b","a","u","v","v","v","t","b","t"], "cost": [935,827,806,951,298,554,896,852,759,853,530,891,942,944,464,952,882,887] }
assert my_solution.minimumCost(**test_input) == 31617

test_input = { "source": "bvbsstasaabvubbaabvbsbsttuvvuutsabbaubau", "target": "sbuutvuttaubsbbsaatbvsbtsvutuutvtabaubat", "original": ["b","b","s","t","a","u","a","v","s","s","v"], "changed": ["s","u","t","v","u","s","s","t","v","b","u"], "cost": [985,604,940,913,910,765,729,905,848,793,468] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "satuaabaavaauussvsvssavtuuvbttassbtususv", "target": "ababsttvsabvuvaatuvtsvtsasbaatavuauvvstv", "original": ["s","u","a","a","a","v","a","u","s","s","v","t","u","u","v","b","t","s","t"], "changed": ["a","b","s","t","v","a","b","v","u","t","t","s","a","s","b","a","a","v","u"], "cost": [848,908,555,510,759,404,799,963,855,901,609,854,878,915,879,594,748,937,942] }
assert my_solution.minimumCost(**test_input) == 27052

test_input = { "source": "sauaavvasvsatabbvuusvatsabssavvtsbvuusva", "target": "abtuuvutubsbbtuttbtubbasuaustsbssatubsvb", "original": ["s","a","a","a","v","t","b","b","v","u","u","s","t","b","v","t"], "changed": ["a","b","u","t","b","b","u","t","t","b","t","u","a","a","s","s"], "cost": [689,325,535,931,528,722,965,786,645,499,791,717,557,988,229,834] }
assert my_solution.minimumCost(**test_input) == 21007

test_input = { "source": "ssautbbbuattvtutbavabtbvbusbsbaavutvbutu", "target": "svbvuttvtbtvuavbvtstutuvutvbasbauvabsvvv", "original": ["s","a","b","u","t","v","t","u","b","a","b","v","b"], "changed": ["v","b","t","t","v","u","a","v","v","t","u","b","s"], "cost": [943,915,778,641,540,872,999,856,979,848,856,935,677] }
assert my_solution.minimumCost(**test_input) == 33036

test_input = { "source": "sstsvvvvvabubtvsvaatsavssbatstbbabbtbvvt", "target": "tattabsubsatbtbbbussususassautbabsbvabvu", "original": ["s","s","v","v","v","v","a","b","s","a","t","s","t","a","b","t","t"], "changed": ["t","a","a","b","s","u","s","a","b","u","s","u","a","b","s","v","u"], "cost": [723,861,682,949,830,969,880,892,750,461,870,592,233,718,967,621,472] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ssuuavtuuutubutvtssbasssvttuvuubbabubvsu", "target": "ustbvvsutaasabtasabuaasuatuaabatubsbtvbt", "original": ["s","u","u","a","t","u","b","s","b","t","u","v","b","a","b","s"], "changed": ["u","t","b","v","a","s","a","a","u","u","a","a","t","b","s","b"], "cost": [709,599,774,993,858,730,987,700,596,200,984,567,656,971,777,790] }
assert my_solution.minimumCost(**test_input) == 23824

test_input = { "source": "suvsavbasssavasvvbttubvbvatbstbabsutvuua", "target": "aaavasusvsatsuvuatbsstbvstuatttuuvubavau", "original": ["s","v","b","a","s","a","t","t","u","b","v","b","b","s","a","u","u"], "changed": ["v","s","u","s","a","t","b","s","s","t","b","v","a","t","u","v","a"], "cost": [944,923,845,911,686,687,403,705,378,929,315,296,484,666,354,375,649] }
assert my_solution.minimumCost(**test_input) == 25662

test_input = { "source": "tavauavbtsuuubtbuaatsbutvastasaavbtbsubs", "target": "stsautbvvtbuvvtstaaubavvuaabubavsvbasvvb", "original": ["t","a","v","v","s","u","b","b","u","t","s","b","u","t","v","s","t","a"], "changed": ["s","t","s","b","t","b","v","s","t","u","b","a","v","v","u","a","b","u"], "cost": [936,867,711,886,565,650,500,694,394,662,948,878,864,993,925,508,714,815] }
assert my_solution.minimumCost(**test_input) == 24476

test_input = { "source": "tbsttbstvtvusvbaavuuuvvuavuuusbusabsubta", "target": "uvvbttvbvtbtausvtavsuavusvusuabuvtutttas", "original": ["t","b","s","u","v","a","a","v","u","u","a","s","b","s","b","t"], "changed": ["u","v","v","t","u","v","t","a","v","s","s","a","u","t","t","a"], "cost": [409,241,815,861,536,968,983,726,882,674,981,516,918,653,368,845] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "tsauvattvvavaasbutvuavvvttuvasavbvavtsaa", "target": "vbtsubbbbbavvvbsvstavasaaaatsattvbtubsvs", "original": ["t","s","u","a","t","v","a","b","u","v","u","v","v","t","a","a","b"], "changed": ["v","b","s","b","b","b","v","s","v","t","a","a","s","a","s","t","v"], "cost": [731,965,614,651,952,991,940,606,664,261,468,295,202,675,921,628,690] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "tsvsstututatsbvatauatsausaubsuuassssbuts", "target": "assutuavuvusbubbtavsavbvusvbvtbubvvuvtvb", "original": ["t","v","s","s","t","u","t","a","s","b","v","a","s","u","a","u","u","b"], "changed": ["a","s","u","t","u","a","v","u","b","u","b","b","v","v","s","t","b","v"], "cost": [924,489,946,903,425,474,965,605,168,870,992,903,367,995,425,580,918,991] }
assert my_solution.minimumCost(**test_input) == 23945

test_input = { "source": "ttuvauavausttvusavuvsuababtubbbvvsttbasv", "target": "butttussvtvbbtbtasuusstattuvvvuavbtsbttu", "original": ["t","t","u","a","a","u","s","v","v","u","a","b","b","u","b","b","v","s","t"], "changed": ["b","u","t","s","v","b","t","s","u","s","t","a","t","v","v","u","a","b","s"], "cost": [790,396,583,83,931,950,760,364,698,503,957,984,611,688,1000,986,679,913,906] }
assert my_solution.minimumCost(**test_input) == 25663

test_input = { "source": "tuasbutsuubbvauvautsbtabsaaauubbvaavtuua", "target": "tvauvutvbbavuatsbaatvtbavatavtsvttttuvta", "original": ["u","s","b","u","v","u","v","a","u","t","b","s","a","b","v","t"], "changed": ["v","u","v","b","u","t","s","b","a","a","a","v","t","s","t","u"], "cost": [958,880,986,571,311,294,673,433,733,984,444,576,666,847,516,866] }
assert my_solution.minimumCost(**test_input) == 21164

test_input = { "source": "tvsbbttvsvubbtasvbusataaatautauavvstsbub", "target": "tbttvaavutvbstvutavavtbuvtuabsubsuvbtusa", "original": ["v","b","s","u","b","v","s","a","a","a","u","t","v","v","s","s","u","b"], "changed": ["b","v","u","v","s","t","a","v","b","u","a","b","s","u","v","t","s","a"], "cost": [977,323,878,825,625,908,794,831,973,881,946,981,437,904,564,826,720,583] }
assert my_solution.minimumCost(**test_input) == 29347

test_input = { "source": "uatavuaavatstabvtvabbbuvatvabbauvsvtauuu", "target": "ustbbuvbtusutuutvsuttbuubuuubasvubuubusb", "original": ["a","a","v","a","v","a","t","b","t","b","v","t","s","u","u"], "changed": ["s","b","b","v","t","u","s","u","v","t","u","u","b","s","b"], "cost": [681,801,894,221,732,732,984,989,750,705,181,993,888,957,912] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ubvtusbavavtbssuutvsvasttbauvtvttsvtttss", "target": "usasbvasuttsbvvuuvvtubssuuuuvuvubtsbsstu", "original": ["b","t","a","v","a","s","s","t","b","a","t","v","s"], "changed": ["s","s","s","u","t","v","t","u","u","u","b","s","u"], "cost": [933,864,772,686,918,885,923,892,538,120,913,892,441] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "ubvuasvuvuavasvvasausabbtausaaubbvbtuubv", "target": "sbbutubbvtvauatbavstvbttavbubvsvsutuavta", "original": ["u","v","a","s","u","a","v","a","s","s","a","a","b","b","u","u"], "changed": ["s","b","t","u","b","v","a","u","a","v","s","b","t","s","a","v"], "cost": [951,655,564,597,402,910,850,664,352,937,698,281,997,798,368,963] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "utauutasstbuubsussstaauatvaavuuabvvbvaba", "target": "vttavbbbvbbbvuaavauubbsavaststtatsbssaab", "original": ["a","u","t","a","s","s","s","t","v","a","u","b","v","b","v","b"], "changed": ["t","a","b","b","b","a","v","v","a","s","t","t","b","s","s","a"], "cost": [862,888,579,525,903,443,828,892,953,879,855,705,961,438,478,998] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "uttbbsvttssubvbbaabsavaabvsvbbbbbatvbtsu", "target": "tatsstaubbtbvsabvasbubvvbutasssvttuvvtvs", "original": ["u","t","b","s","v","t","t","u","b","v","b","a","s","v","v","b","a","s","u"], "changed": ["t","a","s","t","a","u","b","b","v","s","a","v","b","b","u","t","t","v","s"], "cost": [880,822,798,549,420,189,730,621,865,189,950,921,887,816,772,69,907,868,715] }
assert my_solution.minimumCost(**test_input) == 23971

test_input = { "source": "utvsausubbtuasvtuttatbtasuvbtuuubsatabau", "target": "tstsatsbsttaatasbvvsabbabbtabtvbvuaavaau", "original": ["u","b","b","u","s","v","u","t","a","t","s","b","u","b","s","a"], "changed": ["t","s","t","a","t","a","b","v","s","a","b","a","v","v","u","v"], "cost": [425,837,948,892,923,403,619,690,775,951,577,1000,816,999,602,800] }
assert my_solution.minimumCost(**test_input) == 29865

test_input = { "source": "uvtavsbvvvvavsstavustttuuvvavatattbavttv", "target": "vvbuuutbtvbtutatuttvsssvtvsbbvbbvuausavu", "original": ["t","a","v","s","b","v","v","a","s","s","u","s","t","u","v","a","t","t","b"], "changed": ["b","u","u","u","t","b","t","t","t","a","t","v","s","v","s","b","v","u","a"], "cost": [984,969,379,449,842,818,399,954,718,823,932,935,405,591,643,965,1000,700,189] }
assert my_solution.minimumCost(**test_input) == 27084

test_input = { "source": "vabsuaavabatbastaauaaaututtutsvuusatavas", "target": "svubbsaavaubbbvasatssvvubtsssabsabsbstau", "original": ["a","s","u","a","v","b","a","s","t","u","u","t","u","t","s","v","u","t","v","s"], "changed": ["v","b","b","s","a","a","u","v","a","t","v","u","s","s","a","b","a","b","t","u"], "cost": [948,531,696,662,908,460,829,859,857,374,1000,996,356,810,804,751,988,815,933,924] }
assert my_solution.minimumCost(**test_input) == 27967

test_input = { "source": "vsvstbbutastuuaubuausuuavvttvabvsaavbtvs", "target": "vbbtbuatasbauavbbabbbvbutaavsvtubvbuttst", "original": ["s","v","s","t","b","b","u","a","t","u","a","u","a","u","a","v","v","b","v"], "changed": ["b","b","t","b","u","a","t","s","a","a","v","b","b","v","u","t","s","t","u"], "cost": [510,990,975,894,921,775,819,665,76,509,943,691,757,617,773,404,777,932,837] }
assert my_solution.minimumCost(**test_input) == 25040

test_input = { "source": "vusbbaubbusbbtusttbtavsavbbbausavbausbub", "target": "uvvbsututvavautuatuussbbttbaaaasbbuvavaa", "original": ["u","b","a","u","b","b","s","b","b","t","t","s","a","v","u","a","v"], "changed": ["v","s","u","t","u","t","a","v","a","u","a","b","b","t","a","s","b"], "cost": [555,920,950,949,936,35,455,910,746,791,661,864,926,11,833,870,854] }
assert my_solution.minimumCost(**test_input) == 26439

test_input = { "source": "vvabsutautvsutvavtsvstabvbvtutbvuautaatb", "target": "taasvsstbstasbtuauvtbtusbssbbssbuusuvbbu", "original": ["v","b","s","u","t","u","v","t","a","t","s","v","v","a"], "changed": ["a","s","v","s","s","b","t","b","u","u","b","s","b","b"], "cost": [813,860,971,768,419,950,866,741,989,756,325,806,507,571] }
assert my_solution.minimumCost(**test_input) == 36258

test_input = { "source": "vvvsaavtavaabtssasstbvuusbubbbsastvttbba", "target": "utssutvbabttvstsbbusttuuutvvbtasvuvbvvav", "original": ["v","a","a","v","b","t","s","a","s","b","s","u","s","a","s","t","t","b","a"], "changed": ["t","u","t","b","v","s","t","b","b","t","u","v","a","s","v","b","v","a","v"], "cost": [722,823,981,465,482,999,572,191,410,968,377,549,658,692,898,263,928,197,831] }
assert my_solution.minimumCost(**test_input) == 22953

test_input = { "source": "asmlmoumomvummakmlbabvmvvavlavtsvbvssuumsllttsusts", "target": "asmlmoumomvummakmlbabvmvvaolklllvbsltuomkslvmmusts", "original": ["vlavtsvbvssuumslltts","mtmubkasuvumkobbmsmo","vsbbvauauvuvsauaastl","uovumoluksslvkvlkmam","smsvsuubusskmublvvst","momuatbkubosmmavvssk","mommltotttbtvlvalsbt","vbbbuvslutblvvkvtmmo","boaosasttvtvtabtubab","mbtkumblvbasoobaauvm","vbotklaoltambktlulot","vluamsokkbaalsmmalav","mttmbuosbmlttabmbabl","sskvkbmlabaulluomovt","lstbuomkaoatmavsmvml"], "changed": ["mtmubkasuvumkobbmsmo","vsbbvauauvuvsauaastl","uovumoluksslvkvlkmam","smsvsuubusskmublvvst","momuatbkubosmmavvssk","mommltotttbtvlvalsbt","vbbbuvslutblvvkvtmmo","boaosasttvtvtabtubab","mbtkumblvbasoobaauvm","vbotklaoltambktlulot","vluamsokkbaalsmmalav","mttmbuosbmlttabmbabl","sskvkbmlabaulluomovt","lstbuomkaoatmavsmvml","olklllvbsltuomkslvmm"], "cost": [9758,7133,9355,8885,6055,7360,9168,9288,7422,6995,8167,6154,6939,6343,9733] }
assert my_solution.minimumCost(**test_input) == 118755

test_input = { "source": "bkmltoaakmatkvllubamuvbmkolamvolsaottsokbmutktsvlo", "target": "skmltoaakmatkvllubamuvbmkolamvolsosuataatovmktsvlo", "original": ["aottsokbmut","ktuumtblakk","mkumbambakt","tubtvmuuoat","kkkksosllks","sastauoammb","sbomolbklsk","kaabakosmsb","ltaltkmukoa","lmlaovmluta","kusalltssaa","mattouslbou","obaavmovsal","bk","ko"], "changed": ["ktuumtblakk","mkumbambakt","tubtvmuuoat","kkkksosllks","sastauoammb","sbomolbklsk","kaabakosmsb","ltaltkmukoa","lmlaovmluta","kusalltssaa","mattouslbou","obaavmovsal","osuataatovm","ko","sk"], "cost": [5819,9018,7484,6655,5163,5728,3077,7032,4630,8093,6974,5623,9179,7307,9974] }
assert my_solution.minimumCost(**test_input) == 101756

test_input = { "source": "blvalvmkosattusaubkbuvusmoolmkloavaskmkbovkkbvtaas", "target": "blvalvmkosattlooutkvsmabuvaumkloavaskmkbovkkbvtaas", "original": ["usaubkbuvusmoolm","stvkuuablkvlvbuv","laosbokmbsusulta","tosusvtstuousmtv","tkbbalmtoubtmlvk","vauvllvbootbvtsv","malabvmoaavulomv","ootsoksuosvlakov","alaobmvbttmtobvl","oauamtksvbuovmbt","ubtlssmbbaloatsa","sstskkmtkoobaavt","avsskubbbtossbsu","aumbsbautvkmsauu","btsuvmosbtomvmma"], "changed": ["stvkuuablkvlvbuv","laosbokmbsusulta","tosusvtstuousmtv","tkbbalmtoubtmlvk","vauvllvbootbvtsv","malabvmoaavulomv","ootsoksuosvlakov","alaobmvbttmtobvl","oauamtksvbuovmbt","ubtlssmbbaloatsa","sstskkmtkoobaavt","avsskubbbtossbsu","aumbsbautvkmsauu","btsuvmosbtomvmma","looutkvsmabuvaum"], "cost": [8903,5338,8835,8645,8789,7933,8044,3865,7564,5782,9245,9165,8886,7691,8039] }
assert my_solution.minimumCost(**test_input) == 116724

test_input = { "source": "mobbmmmsabbomsbukkotbttvsuoubtvuabaktsuoltvamlltbv", "target": "mobbmmmsauotksusvmvtbmaovtsvtaklabaktsuoltbamtumtl", "original": ["bbomsbukkotbttvsuoubtvua","sbuastublskotvtotmokuota","kssvtltakbtmlbmtoskaousb","vuososkmtvsobkbvuvbklvbv","vtsvllsklslkbulusbuastlm","bttokabvovvktkavatskoamt","lbmobulvomkovaalbtkoukso","tmmlusaokamvstsmuksmbulu","lkktooukbstvkumvbbsllaas","mbvtkltbvuumuvobstooammv","skovmvassobkbutolttvkokb","olastbtotmlusbmlukmokubl","kvbomsvuaskvkvvmssavubtt","buusuklobuoukatusulotmks","vamlltbv"], "changed": ["sbuastublskotvtotmokuota","kssvtltakbtmlbmtoskaousb","vuososkmtvsobkbvuvbklvbv","vtsvllsklslkbulusbuastlm","bttokabvovvktkavatskoamt","lbmobulvomkovaalbtkoukso","tmmlusaokamvstsmuksmbulu","lkktooukbstvkumvbbsllaas","mbvtkltbvuumuvobstooammv","skovmvassobkbutolttvkokb","olastbtotmlusbmlukmokubl","kvbomsvuaskvkvvmssavubtt","buusuklobuoukatusulotmks","uotksusvmvtbmaovtsvtakla","bamtumtl"], "cost": [8432,9912,7958,9938,8402,7223,5772,9501,8749,8597,6195,7504,7103,9582,8898] }
assert my_solution.minimumCost(**test_input) == 123766