## WBAHD - Weak Bridge Ahead

no tags

You are on a highway of two lanes. There is a bridge on the highway which is almost broken. It is so weak that at most one car can stay over the bridge at any moment. Few cars are waiting on both ends of the bridge forming a queue and they want to cross the bridge. Cars on the same side of the bridge are in the same lane and cars on different sides of the bridge are in different lanes. No car can overtake any other car or change its lane; otherwise, they will be fined. So only the cars which are at the front of their queue have the chance to cross the bridge. Given the time needed for each car to cross the bridge, find the optimal order of cars passing the bridge such that the maximum waiting time of a car is minimized [See sample input/output and the explanation section for better understanding]. Waiting time for a car is equal to the time it has to wait before stepping onto the bridge. You can assume that the time needed for a car to get to the bridge or to get down from the bridge is negligible.

### Input

The first line of input contains two integers, T, denoting the number of test cases. Then for each test case you will first be given two integers, N & M. Here N denotes the number of cars waiting in the left side of the bridge and M denotes the number of cars waiting in the right side of the bridge. It follows a single line having N integers. i-th integer of this line denotes the time needed for the i-th car to pass the road in seconds [ the car at the front of the queue is considered to be the 1st car ]. Then a line follows having M integers describing the second queue in exactly the same way.

### Output

For each test case print an integer in the form “Case x: k” where x is equal to the number of test case starting from 1 and k is equal to the minimum possible waiting time of the car which has the maximum waiting time.

### Constraint

`1 ≤  T ≤  101 ≤  N ≤  100001 ≤  M ≤  100001 ≤  Time needed for a car to cross the bridge ≤  1000000000`

### Example

`Input:2 1 1 5 3 3 2 9 11 4 10 12`
`Output:Case 1: 3Case 2: 34`

Explanation:

In the first test case, it’s better to first let the car which takes 3 seconds to pass the bridge pass first. So the other car has to wait for 3 seconds.

``````4 11 9 ### ------
------ ### 10 12
``````

Now let one car from the left side pass the bridge:

``````  4 11 ### ------
------ ### 10 12
``````

This car had to wait for 0 seconds.

Then let one car from the right side pass the bridge:

``````  4 11 ### ------
------ ### 12
``````

This car had to wait for 9 seconds.

Then let another car from the left side pass the bridge:

``````    4  ### ------
------ ### 12
``````

This car had to wait for 19 seconds.

After that, let the last car from the left side pass the bridge.

``````       ### ------
------ ### 12
``````

This car had to wait for 30 seconds.

Finally, let the last car from the right side pass the bridge and you are done.

``````       ### ------
------ ###
``````

This car had to wait for 34 seconds.

So 34 is the maximum waiting time which we tried to minimize. It’s not possible to get a smaller answer by any other ordering of the cars crossing the bridge.