You are given a string target, an array of strings words, and an integer array costs of the same length, where costs[i] represents the cost of using the string words[i].

Starting with an empty string, you can repeatedly append any string from words. Appending words[i] adds costs[i] to the total cost. You may select each string from words any number of times.

Return the minimum total cost required to construct target. If it is impossible to form target, return $-1$.

Constraints:

• $1 \leq$ target.length $\leq 2000$

• $1 \leq$ words.length = costs.length $\leq 50$

• $1 \leq$ words[i].length $\leq$ target.length

• target and words[i] consist only of lowercase English letters.

• $1 \leq$ costs[i] $\leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.