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   10
1   N   10000
1   M   10000
1   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: 3
Case 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.

On the second case, initially, the highway looks like this: [“-” sign indicates road and “#” sign indicates bridge]


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.

 

 

 

 

 

 

 


hide comments
aquib_ansari: 2018-07-08 17:01:01

i'm getting TLE! Help...

Vladimir: 2016-10-05 20:27:06

Too easy, should be moved to basics/tutorial

Reply: Done :)

Last edit: 2016-10-06 03:24:08
Paul Redman: 2016-10-05 09:19:16

@Bertho_Coder The input example should be as below to match the description I think?
2
1 1
5
3
3 2
9 11 4
10 12

Reply: Oh yes! Thanks a lot!

Last edit: 2016-10-05 17:33:25

Added by:Bertho Coder
Date:2016-10-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU