Minimum Substring Conversion Cost

You are given two strings source and target of equal length n, and three parallel arrays original, changed, and cost: rule i converts the substring original[i] into changed[i] (both the same length) at cost cost[i].

Starting from source, you may apply any number of operations. Each operation picks a substring equal to some original[j] and replaces it with changed[j], paying cost[j]. Across all operations, any two picked substrings must be either

• disjoint (their index ranges do not overlap), or
• identical (exactly the same index range, operating repeatedly on the same slice).

Return the minimum total cost to turn source into target, or -1 if it is impossible.

Examples

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: b->c (5), c->e->b (1+2), d->e (20) converts "abcd" to "acbe" for 28.

Example 2

Input: source = "abcdefgh", target = "acdeeghh",
       original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
Output: 9
Explanation: "bcd" -> "cde" (1), then "fgh" -> "thh" -> "ghh" (3 + 5) on the same slice.

Example 3

Input: source = "abcdefgh", target = "addddddd",
       original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
Output: -1
Explanation: The two needed slices overlap without being identical.