Word Puzzle is a puzzle to generate a given sentence using pieces of given word. At this point, we assume that there are infinite numbers of pieces for each given word. For example, when given words are [“ba”, “na”, “n”, “a”], there are infinite pieces of ba, na, n, and a. At this point, if the sentence to generate is banana, it can be generated by using 4 pieces of ba, na, n, and a. Also, you can generate banana using 3 pieces of ba, na, and na. Given an array strs containing available pieces of words and sentence to generate t as parameters, write a function solution to return the minimum number of pieces to generate given sentence. If the given sentence cannot be generated, return -1.

Constraints

• strs is an array containing available pieces of words, and its length is between 1 and 100.
• There are no duplicated elements in strs.
• Pieces of words are in string format, and length of all pieces is between 1 and 5.
• t is a sentence to generate, and its length is between 1 and 20,000.
• All strings consist of lower-case alphabet only.

Examples

Example #1
This is the same with an example in problem statement.

Example #2
apple can be generated by using 2 pieces of ap and ple, return 2.

Example #3
Since banana cannot be generated using given words, return -1.