<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 Trie:
    def __init__(self):
        self.c = defaultdict(Trie)
        self.cost = math.inf
    def add(self, w, cost):
        cur=self
        for ch in w: cur=cur.c[ch]
        cur.cost = min(cur.cost, cost)

MAXL = 500

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        trie=Trie()
        longw = []
        for i in range(len(words)):
            w,c = words[i], costs[i] 
            if len(w) <= MAXL: trie.add(w,c)
            else: longw.append(i)
        n=len(target)
        indexes=[[] for _ in range(n)]
        for wid in longw:
            w = words[wid]
            table, i = [0], 0
            for ch in w[1:]:
                while i and w[i]!=ch: i=table[i-1]
                if w[i]==ch: i+=1
                table.append(i)
            # print(w, tabele)
            i=0
            for j,ch in enumerate(target):
                while i and w[i]!=ch: i=table[i-1]
                if w[i]==ch: i+=1
                if i==len(w): 
                    indexes[j-len(w)+1].append(wid)
                    i=table[i-1]
        # print(indexes)
        
        @lru_cache(None)
        def dp(i):
            if i==n: return 0
            t=trie
            cost=math.inf
            for wid in indexes[i]: cost=min(cost, costs[wid] + dp(i+len(words[wid])))
            for j in range(i, n):
                ch = target[j]
                if ch not in t.c: break
                t=t.c[ch]
                cost=min(cost, t.cost + dp(j+1))
            return cost
        res=dp(0)
        return -1 if isinf(res) else res
        
83600