Best Alignment

Given two sequences of positive integer A = { a₁, a₂, ...,a_N } and B = { b₁, b₂ ..., b_M } where N ≥ M, you have to find the value of the best alignment of A and B.

An A-B alignment is defined as below:

• Insert one or more zeroes into B in any position (and become B') such that the size of B' is equal to the size of A.
• The value of this A-B alignment is the sum of all multiplication of a_i with b'_i for all i = 1..N.

An alignment is defined as best if it has the greatest value among all other possible alignments.

For example, let A = { 6, 1, 5, 3, 7, 4 } and B = { 3, 4, 5 }. There are plenty of ways to align B with A, e.g.:

• A  = 6 1 5 3 7 4
  B' = 3 4 5 0 0 0

  The value of this alignment is (6 * 3) + (1 * 4) + (5 * 5) = 47.

• A  = 6 1 5 3 7 4
  B' = 0 3 0 4 0 5

  The value of this alignment is (1 * 3) + (3 * 4) + (4 * 5) = 35.

• A  = 6 1 5 3 7 4
  B' = 3 0 4 0 5 0
  

  The value of this alignment is (6 * 3) + (5 * 4) + (7 * 5) = 73. Apparently, this is the highest value we can get by aligning B with A.
  
  
• ...and many other alignments.

Given A and B, determine the value of the best alignment of A and B.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with two integers N and M (1 ≤ M ≤ N ≤ 1,000) denoting the size of A and B respectively. The next line contains N integers a_i (1 ≤ a_i ≤ 1,000) denoting the member of A where i = 1..N. The following line contains M integers b_j (1 ≤ b_j ≤ 1,000) denoting the member of B where j = 1..M.

Output

For each case, output in a line the "Case #X: Y" where X is the case number starts from 1, and Y is the value of best alignment for each case.

4
6 3
6 1 5 3 7 4
3 4 5
5 5
6 2 4 5 4
3 3 6 1 2
4 1
70 40 100 80
3
5 2
15 130 35 800 1
100 10

Case #1: 73
Case #2: 61
Case #3: 300
Case #4: 80010

Explanation for the 2^nd sample input.

There is only one possible alignment (A and B are already in equal size).

Explanation for the 3^rd sample input.

B only has 1 element, thus the best alignment can be found by aligning this value with the largest value in A.

Explanation for the 4^th sample input.

The best alignment is:

 15 130  35 800   1
  0   0   0 100  10