1. You are given two arrays -
The first array(keys), which is sorted and has distinct integers, represents search keys.
Second one(freq) represents frequency counts, where freq[i] is the number of searches to keys[i].
2. A binary search tree is constructed containing all keys and the total cost of searches is minimum.
3. The cost of a BST node is the level of that node multiplied by its frequency.
4. You have to find the minimum cost of all searches.Input Format
A number N a1 a2.. N integers b1 b2.. N numbers
Output Format
Check the sample output and question video.
Constraints
1 <= N <= 1000 1 <= keys[i],freq[i] <= 1000
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
9 1 3 4 5 6 7 8 9 11 3 6 4 8 7 3 7 4 7
Output
125