A. Array Merge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two arrays $$$A$$$, $$$B$$$ of length $$$n$$$ and $$$m$$$ separately, you have to merge them into only one array $$$C$$$ (of length $$$n+m$$$) obeying the rule that the relative order of numbers in the same original array does not change in the new array.

After merging, please calculate the $$$cost=\sum_{i=1}^{n+m} i \times C[i] $$$ and output it.

If there are multiple $$$cost$$$s, please output the minimum of them.

Input

The first line of input file contains an integer $$$T$$$ ($$$1\le T\le 50$$$), describing the number of test cases.

Then there are $$$3 \times T$$$ lines, with every three lines representing a test case.

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^5$$$) as described above.

The second line of that contains $$$n$$$ integers, $$$i^{th}$$$ of which represents the $$$A[i]$$$.

The third line of that contains $$$m$$$ integers, $$$i^{th}$$$ of which represents the $$$B[i]$$$.

The numbers in both array have range in $$$[0,10^8]$$$.

It is guaranteed that the sum of $$$n+m$$$ in all cases does not exceed $$$10^6$$$.

Output

You should output exactly $$$T$$$ lines. For each case, print Case $$$d$$$: ($$$d$$$ represents the order of test case) first and then print a number representing the minimum $$$cost$$$ on the same line.

Example
Input
2
2 2
5 3
4 5
3 3
1 3 5
2 6 4
Output
Case 1: 40
Case 2: 75
Note

Sample 1: Considering merging (5) (3) and [4] [5], we have following valid methods:

  • (5) (3) [4] [5], $$$1 \times 5+2 \times 3+3 \times 4+4 \times 5=43$$$
  • (5) [4] (3) [5], $$$1 \times 5+2 \times 4+3 \times 3+4 \times 5=43$$$
  • (5) [4] [5] (3), $$$1 \times 5+2 \times 4+3 \times 5+4 \times 3=40$$$
  • [4] (5) (3) [5], $$$1 \times 4+2 \times 5+3 \times 3+4 \times 5=43$$$
  • [4] (5) [5] (3), $$$1 \times 4+2 \times 5+3 \times 5+4 \times 3=41$$$
  • [4] [5] (5) (3), $$$1 \times 4+2 \times 5+3 \times 5+4 \times 3=41$$$

So the answer is the minimum of the numbers above, 40.