## BOBERT - Stick values

no tags

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 Lx can cover any interval of the array whose length is equal to the length of the stick (it can cover Lx 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 Lx covering the interval [lo, hi] is equal to: Lx * (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

### Input

9
2 6 3 1 8 4 3 5 6
4
2 3 2 2

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```