On a sunny day, Stjepan and Bobert were arguing over their problem solving skill under a big apple tree. Bobert brought up a nice problem he had just recently solved and claimed that Stjepan could not solve it. Stjepan is desperate and needs your help. Here is Bobert's problem:

Given an array of N (1 <= N <= 10^5) numbers (0 <= ai <= 10^9) and K (1 <= K <= 20) sticks of a certain length Li (0 <= Li <= N, such that the sum of all lengths is equal to N), find the best possible distribution of the sticks among the array such that:

1. a stick of length L_x can cover any interval of the array whose length is equal to the length of the stick (it can cover L_x consecutive numbers of the array).
2. all sticks must be used and can not overlap or leave the borders of the array.
3. the value of a stick of length L_x covering the interval [lo, hi] is equal to: L_x * (max[lo, hi] - min[lo, hi]). Note that: max = largest element of the array inside the interval and min = smallest element of the array inside the interval.
4. the sum of all stick values must be as large as possible.

Note: double-check your complexity

Input

The first line contains an integer N.

The second line contains N numbers representing the array.

The third line contains an integer K.

The fourth line contains K numbers representing the stick lengths.

Output

The only line should contain the solution - the maximum sum of stick values as explained in the task.

Example

Input:
9
2 6 3 1 8 4 3 5 6
4
2 3 2 2
Output:
33