402922: GYM100947 J Killing everything

There are many enemies in the world such as red coders and hackers. You are trying eliminate everybody. Everybody is standing on a road, which is separated into 10⁹ sections. The sections are numbered 1, 2, 3, 4, …10⁹ from west to east. You want to kill N enemies. The i^th enemy will be standing on the section A_i. In order to kill the enemies, you prepared P small bombs and Q large bombs. You can choose a positive integer w as a parameter for energy consumption. Then, a small bomb can kill all enemies in at most w consecutive sections, and a large bomb can kill all enemies of at most 2w consecutive sections.

Enemies can be killed by more than one bomb. You want to kill all enemies. Since it is expected that many civilians will walk down that road, for the sake of safety, you have to fix the positions of the bombs and minimize the value of w.

So you decided to Write a program that, given information of the enemies and the number of bombs, determine the minimum value of w so all enemies can be killed.

The input consists of several test cases, the first line contains the number of test cases T. For each test case: The first line of input contains three space separated integers N, P, Q (1 ≤ N ≤ 2000, 0 ≤ P ≤ 10⁵, 0 ≤ Q ≤ 10⁵), where N is the number of the enemies, P is the number of small bombs, and Q is the number of large bombs.

The i^th line (1 ≤ i ≤ N) of the following N lines contains an integer A_i, the section where the i^th enemy will be standing.

Output: For each test cases print the solution of the problem on a new line.

1
3 1 1
2
11
17

4

In the sample test case you have 3 enemies at positions: 2, 11, 17.

For w = 4, one possible solution is to throw one small bomb on segment 1 - 4, and one large bomb on segment 11 - 18. This configuration will kill all three enemies.

There is no configuration with w < 4 that can kill them all.