Jumping Frogs

At time 0, R red frogs and G green frogs are sitting on a straight line. All the positions of the frogs are non-negative integer numbers. Every second, all the frogs jump. Each of the frogs has its own velocity, i.e., every second the i-th frog jumps Vi units to its left or right depending on the color. Every red frog jumps to its right, and every green frog jumps to its left. The line is divided into N + 1 contiguous segment. The left end of the first segment is always 0 and the right end of the N + 1-st segment is 109. The segments are denoted by a sequence of N positive integers. For example, if N = 1 and the sequence has 1 integer number 10, then there are two segments, one is from 0 to 10 and another is from 10 to 109, both inclusive. You are given the initial positions of all the R+G frogs and a sequence of positive integers describing the segments. Find the minimum time it will take for all the frogs to reach a single segment. A frog is said to be on a segment if and only if it’s sitting on some points inside the segment (including the endpoints). Please note that a frog is not said to be inside a segment when it’s jumping. Please note that, when a frog is on any of the N intermediate boundary points, they can be considered to be part of either the left or the right segment. Input Input starts with a single positive integer, T ≤ 10, on a single line, denoting the number of test cases. The first line of each test cases will be a blank line. Next line will contain three positive integers R, G and N (1 ≤ R, G ≤ 100, 000, 1 ≤ N ≤ 100, 000). Next five lines will be as follows:

1. R non negative integers, where the i-th integer represents the position of the i-th red frog.
2. R non negative integers, where the i-th integer represents the velocity of the i-th red frog.
3. G non negative integers, where the i-th integer represents the position of the i-th green frog.
4. G non negative integers, where the i-th integer represents the velocity of the i-th green frog.
5. A sequence of N positive integers describing the segments. All the numbers are greater than 0 and are less than 109 Note that, every frogs’ position and velocities are between 0 and 109, inclusive. Please note that the input file is around 4 MB, use faster input/output routine.(i.e. scanf/printf instead of cin/cout for c++) Output For every case print the output in format, ‘Case X: Y ’, where X is the number of test case, starting from 1 and Y is the minimum time it takes for all the frogs to reach a single segment. If it’s impossible for all the frogs to reach a single segment, then Y should be ‘-1’. Sample Input 2 111 10

2/2 10000 20 10000 1000000 221 12 99 100 1000 1001 100 200 100 Sample Output Case 1: 0 Case 2: 1