You are given a list of distinct words and a corresponding list of positive costs. Construct a binary search tree using all words such that its inorder traversal gives the words in lexicographical order.

If a word is placed at level L, where the root is at level 0, its contribution to the total cost is (L + 1) * cost. Return the minimum possible total cost among all valid binary search trees.

Method Signature

long minimumCostBST(List<String> words, List<Integer> costs)

Parameters

• words contains distinct lowercase words.
• costs contains the positive cost of each corresponding word.
• words.get(i) has cost costs.get(i).

Return Value

• Return the minimum total weighted cost of any valid binary search tree.

Rules

• The tree must contain every word exactly once.
• The inorder traversal of the tree must list the words in lexicographical order.
• The input order of words does not define the binary search tree order.
• Each cost stays attached to its corresponding word when words are considered in lexicographical order.
• The root is at level 0.
• A word at level L contributes (L + 1) * cost(word) to the answer.
• If multiple tree structures give the same minimum cost, only the minimum cost is returned.

Constraints

• 1 ≤ words.size() ≤ 300
• costs.size() == words.size()
• 1 ≤ words.get(i).length() ≤ 50
• 1 ≤ costs.get(i) ≤ 1,000,000
• words contains distinct lowercase English words.

Examples

Example 1

Input:

minimumCostBST(words = ["cat", "ant", "dog"], costs = [5, 2, 4])

Output:

17

Explanation:

In lexicographical order, the words are ["ant", "cat", "dog"]. Their corresponding costs are [2, 5, 4]. One optimal tree places "cat" at level 0, "ant" at level 1, and "dog" at level 1. The total cost is 1 * 5 + 2 * 2 + 2 * 4 = 17.

Example 2

Input:

minimumCostBST(words = ["mango", "kiwi", "orange", "grape"], costs = [8, 3, 6, 2])

Output:

32

Explanation:

In lexicographical order, the words are ["grape", "kiwi", "mango", "orange"]. Their corresponding costs are [2, 3, 8, 6]. One optimal tree places "mango" at level 0, "kiwi" and "orange" at level 1, and "grape" at level 2. The total cost is 1 * 8 + 2 * 3 + 2 * 6 + 3 * 2 = 32.

Example 3

Input:

minimumCostBST(words = ["a"], costs = [10])

Output:

10

Explanation:

There is only one word, so it must be the root. Its contribution is 1 * 10 = 10.