Minimum total cost to convert one string into another using weighted character rules

You are given two strings, `source` and `target`, of the same length `n`, both made of lowercase English letters. You are also given a set of character conversion rules as three parallel lists `original`, `changed` and `cost`: rule `j` says that a single character equal to `original[j]` may be replaced by `changed[j]`, and each such replacement costs `cost[j]`. You may apply rules any number of times, at any positions, in any order. Each application changes one character at one position and adds that rule's cost to the total. Return the minimum total cost needed to turn `source` into `target`, or `-1` if it cannot be done. ### Function Signature ```python def minimum_conversion_cost(source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int: ``` ### Rules - Rules are directed: a rule from `a` to `b` does not allow changing `b` into `a`. - Rules may be chained at one position: with a rule from `a` to `c` and another from `c` to `b`, a position holding `a` can become `b` by applying both and paying both costs. - Several rules may share the same `original` and `changed` pair with different costs; any of them may be used. - A position where `source` and `target` already agree costs nothing. - If even one position cannot be converted, the answer is `-1`. ### Constraints - `1 <= n <= 10^5` and `len(source) == len(target) == n` - `1 <= len(original) == len(changed) == len(cost) <= 2000` - Every `original[j]` and `changed[j]` is a single lowercase English letter, and `original[j] != changed[j]` - `1 <= cost[j] <= 10^6` - The answer can reach about `2.5 * 10^12`, which exceeds `2^31 - 1`; it always fits within `2^53`, so return it as a plain integer. ### Examples Example 1 ```text Input: source = "aab", target = "ccb", original = ["a", "b", "a"], changed = ["b", "c", "c"], cost = [1, 2, 5] Output: 6 ``` Changing `a` to `c` directly costs 5, but going from `a` to `b` and then from `b` to `c` costs 1 + 2 = 3. Positions 0 and 1 each cost 3, and position 2 already matches, so the total is 6. Example 2 ```text Input: source = "ab", target = "ba", original = ["a"], changed = ["b"], cost = [4] Output: -1 ``` Position 0 can become `b` for 4, but no rule or chain of rules turns `b` into `a`, so position 1 cannot be converted. Example 3 ```text Input: source = "ab", target = "bb", original = ["a", "a"], changed = ["b", "b"], cost = [7, 3] Output: 3 ```