<p>You are given a string <code>target</code>, an array of strings <code>words</code>, and an integer array <code>costs</code>, both arrays of the same length.</p>

<p>Imagine an empty string <code>s</code>.</p>

<p>You can perform the following operation any number of times (including <strong>zero</strong>):</p>

<ul>
	<li>Choose an index <code>i</code> in the range <code>[0, words.length - 1]</code>.</li>
	<li>Append <code>words[i]</code> to <code>s</code>.</li>
	<li>The cost of operation is <code>costs[i]</code>.</li>
</ul>

<p>Return the <strong>minimum</strong> cost to make <code>s</code> equal to <code>target</code>. If it&#39;s not possible, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">target = &quot;abcdef&quot;, words = [&quot;abdef&quot;,&quot;abc&quot;,&quot;d&quot;,&quot;def&quot;,&quot;ef&quot;], costs = [100,1,1,10,5]</span></p>

<p><strong>Output:</strong> <span class="example-io">7</span></p>

<p><strong>Explanation:</strong></p>

<p>The minimum cost can be achieved by performing the following operations:</p>

<ul>
	<li>Select index 1 and append <code>&quot;abc&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abc&quot;</code>.</li>
	<li>Select index 2 and append <code>&quot;d&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abcd&quot;</code>.</li>
	<li>Select index 4 and append <code>&quot;ef&quot;</code> to <code>s</code> at a cost of 5, resulting in <code>s = &quot;abcdef&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">target = &quot;aaaa&quot;, words = [&quot;z&quot;,&quot;zz&quot;,&quot;zzz&quot;], costs = [1,10,100]</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>

<p><strong>Explanation:</strong></p>

<p>It is impossible to make <code>s</code> equal to <code>target</code>, so we return -1.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length == costs.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= target.length</code></li>
	<li>The total sum of <code>words[i].length</code> is less than or equal to <code>5 * 10<sup>4</sup></code>.</li>
	<li><code>target</code> and <code>words[i]</code> consist only of lowercase English letters.</li>
	<li><code>1 &lt;= costs[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class TrieNode:
    def __init__(self):
        self.sfx: TrieNode = None
        self.dict: TrieNode = None
        self.children: List[TrieNode] = [None] * 26
        self.word_id: int = -1


class Iterator:
    def __init__(self, start, end):
        self.curr = start
        self.end = end

    def __iter__(self):
        return self

    def __next__(self):
        if self.curr == self.end:
            raise StopIteration
        res = self.curr
        self.curr = self.curr.dict
        return res.word_id


class Trie:
    def __init__(self, words, costs):
        self.count = 0

        self.root = TrieNode()
        self.root.sfx = self.root.dict = self.root
        for i in range(len(words)):
            u = self.root

            for c in words[i]:
                index: int = ord(c) - ord('a')
                if u.children[index] is None:
                    u.children[index] = TrieNode()
                u = u.children[index]
            if u.word_id < 0 or costs[i] < costs[u.word_id]:
                u.word_id = i
        q = deque()
        q.append(self.root)
        while len(q) > 0:
            u = q.popleft()
            for i in range(26):
                v = u.children[i]
                if v is None:
                    continue
                p = u.sfx
                while p != self.root and p.children[i] is None:
                    p = p.sfx
                    if p is None:
                        print()
                if u != self.root and p.children[i] is not None:
                    v.sfx = p.children[i]
                else:
                    v.sfx = self.root
                v.dict = v.sfx if v.sfx.word_id >= 0 else v.sfx.dict
                q.append(v)
        self.curr = self.root

    def suffixesAfterAppending(self, letter):
        index = ord(letter) - ord('a')
        while self.curr != self.root and self.curr.children[index] is None:
            self.curr = self.curr.sfx
        if self.curr.children[index] is not None:
            self.curr = self.curr.children[index]
            start = self.curr if self.curr.word_id >= 0 else self.curr.dict
        else:
            start = self.root
        return Iterator(start, self.root)


class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        trie = Trie(words, costs)
        n = len(target)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = 10 ** 9
            for j in trie.suffixesAfterAppending(target[i - 1]):
                dp[i] = min(dp[i], dp[i - len(words[j])] + costs[j])
        return -1 if dp[n] == 10 ** 9 else dp[n]
51100