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:

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