# Optimal Binary Search Tree

easy

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.

## Constraints

1 <= N <= 1000 1 <= keys[i],freq[i] <= 1000

## Format

### Input

A number N a1 a2.. N integers b1 b2.. N numbers

### Output

Check the sample output and question video.

## Example

Sample Input

9
1
3
4
5
6
7
8
9
11
3
6
4
8
7
3
7
4
7

### Sample Output

125

Question Video