Its the month of May and its too sunny outside. Kaalia is feeling hungry and wants to eat apples. But he is too lazy to go outside and so ordered Dholu Bholu to bring apples.
They went out and saw Raju selling apples and went to buy apples from him. Raju hate's them and doesn't want to sell apples to them. But he knows that if he denies to sell apples, Kaalia would beat him.
So he gave them a task and tried to trick them. He said, if they were able to solve the task, he won't charge any money for the apples; But if they were unable to do so he won't sell apples to them.
The Task is :
They are given an array consisting of N numbers. The array has 1-based indexing. They are also given a bucket consisting of K indices. K is even. They can pick two indices from the bucket at a time and form a pair from them. Picked indices are removed from the bucket and another pair of indices is choosen. This goes on until the bucket is empty. Its easy to see that total K/2 pairs will be formed.
After forming the pairs they do the following :
Initially S is 0.
Each pair will consist of two indices. Consider them as the end points of a subarray in the given array. Take the sum of all the elements in the subarray and add it to S. See sample input explanation for more clarity.
They have to find maximum possible value of S.
Raju thought that Dholu Bholu will not be able to solve the task but he didn't know that they have a Programmer friend.
You being the Programmer friend of Dholu Bholu need to find and print the maximum value of S.
Input :
First line of input consists of T denoting the number of Test Cases.
First line of every Test case consists of N, the number of elements in array.
Next line contains N space seperated integers, denoting the array elements.
Next line contains K, the number of indices in the Bucket.
Next line contains K space seperated integers denoting the elements of the bucket.
Output :
For every test case print a Single value, the maximum possible value of S in a seperate line.
Contraints :
1<= T <= 10
2 <= N <= 105
1 <= Array elements <=106
2 <= K <= N. K is even.
1<= Elements in bucket <= N
Array : 1 2 3 4 5 6 7
Elements in the bucket : 5, 1, 2, 5
Lets say they picked up (5, 5) for the first pair and (1,2) for the second pair.
Sum of subarray (1,2) = 3
Sum of subarray (5,5) = 5
S = 3 + 5 = 8
Note : Above selection of pairs is not optimal for giving maximum value of S. It was just for understanding purpose.
