An interesting game
Xiao Ming recently designs a little game, in front of player there are N small hillsides put in order, now Xiao Ming wants to increase some hillsides to block the player, so he prepared another M hillsides, but he does not hope it will be too difficult,so only K in M hillsides are selected to add at most. Paying attention to the original N hillsides, between each two can add only one hillside. Xiao Ming expects players from the starting place to reach the destination in turn and passes all the hillsides to make his distance travelled longest. Please help Xiao Ming how to add the hillsides that he prepared. Note: The distance between two hillsides is the absolute value of their height difference.
The first line of input is T, (1 <= T <= 100) the number of test cases. Each test case starts with three integers N,M,K (2 <= N <= 1000, 1 <= M <= 1000, 1 <= K <= M and 1 <= K < N), which means that the number of original hillsides, the number of hillsides Xiao Ming prepared and The number of most Xiao Ming can choose from he prepared. Then follow two lines, the first line contains N integers Xi (0 <= Xi <= 30), denoting the height of each original hillside, Note: The first integer is player's starting place and the last integer is player's destination. The second line contains M integers Yi (0 <= Yi <= 30), denoting the height of prepared each hillsides.
For every test case, you should output "Case k: " first in a single line, where k indicates the case number and starts from 1. Then print the distance player can travel longest.
3 2 1 1 6 9 8 2 1 1 6 9 15 3 2 1 5 9 15 21 22
Case 1: 3 Case 2: 15 Case 3: 36