Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2968
Difference Game

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Now you are going to play an interesting game. In this game, you are given two groups of distinct integers and C coins. The two groups, named Ga and Gb respectively, are not empty and contain the same number of integers at first. Each time you can move one integer in one group to the other group. But a move that makes a group empty is considered as invalid. Each move will cost you p coins, and p equals the difference of the size between the two group (take the absolute value. e.g. moving a number from the group of size 4 to the group of size 6 will cost you |4 - 6| = 2 coins, and moving a number between two group with same size will not cost any coins). You can do as many moves as you wish, so long as the total cost does not exceed C.

Let M be the minimum integer in Ga, and N be the maximum integer in Gb. The purpose of this game is to produce a maximum (M - N).


Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 60) which is the number of test cases. And it will be followed by T consecutive test cases.

Each case begin with two integers S (1 <= S <= 20000, indicating the size of Ga and Gb at first) and C (0 <= C <= 1000000). Two lines of S integers follow, representing the numbers in Ga and Gb respectively. All these integers are distinct and are between 1 and 50000, both inclusive.


Results should be directed to standard output. The output of each test case should be a single integer in one line, which is the maximum possible value for M - N after some moves.

Sample Input

1 10
2 10
1 2
3 4

Sample Output



For Sample 1, two groups are of size 1, so no moves can be done because any moving will make Ga or Gb empty, which is not valid. So M = 10, N = 12, M - N = -2.
For Sample 2, one valid steps of moves is:
Move 1 in Ga to Gb, cost 0 coins.
Move 3 in Gb to Ga, cost 2 coins.
Move 4 in Gb to Ga, cost 0 coins.
Then Ga contains 2 3 4, Gb contains 1, M = 2, N = 1, M - N = 1. This is the maximum possible value.

Author: HANG, Hang
Source: The 5th Zhejiang Provincial Collegiate Programming Contest
Submit    Status