<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.child = defaultdict(TrieNode)
        self.idx = -1
        self.output = defaultdict(lambda :inf)
        self.suffix = None
    
class Aho:
    def __init__(self,words,costs):
        self.root = TrieNode()
        for i,word in enumerate(words):
            curr = self.root
            for c in word:
                curr = curr.child[c]
            if curr.idx==-1 or costs[curr.idx]>costs[i]:
                curr.idx = i
            curr.output[len(word)] = min(curr.output[len(word)], costs[curr.idx])
        self.build()
    
    def build(self):
        q = deque([])
        for a,b in self.root.child.items():
            q.append(b)
            b.suffix = self.root
        
        while q:
            curr = q.popleft()
            for c,node in curr.child.items():
                pre = curr.suffix
                while pre and c not in pre.child:
                    pre = pre.suffix
                if pre and c in pre.child:
                    node.suffix = pre.child[c]
                else:
                    node.suffix = self.root
                
                if node.suffix.idx>=0:
                    node.idx = node.suffix.idx
                if node.suffix is not self.root:
                    for a,b in node.suffix.output.items():
                        node.output[a] = min(node.output[a],b)
                q.append(node)
    
    def append(self,node,c):
        while node != self.root and c not in node.child:
            node = node.suffix
        
        if c not in node.child: return self.root
        if c in node.child: return node.child[c]
        return node

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        n = len(target)
        trie = Aho(words,costs)
        dp = [inf]*(n+1)
        dp[0] = 0
        
        curr = trie.root
        for i in range(1,n+1):
            curr = trie.append(curr,target[i-1])
            for a,b in curr.output.items():
                dp[i] = min(dp[i], b+dp[i-a])
        return dp[n] if dp[n]<inf else -1
64800