{"problem":{"name":"J. Killing everything","description":{"content":"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 109 sections. The sections are numbered","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10094J"},"statements":[{"statement_type":"Markdown","content":"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 109 sections. The sections are numbered 1, 2, 3, 4, …109 from west to east. You want to kill N enemies. The ith enemy will be standing on the section Ai. 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. \n\nEnemies 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.\n\nSo 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.\n\nThe 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 ≤ 105, 0 ≤ Q ≤ 105), where N is the number of the enemies, P is the number of small bombs, and Q is the number of large bombs.\n\nThe ith line (1 ≤ i ≤ N) of the following N lines contains an integer Ai, the section where the ith enemy will be standing.\n\nOutput: For each test cases print the solution of the problem on a new line.\n\nIn the sample test case you have 3 enemies at positions: 2, 11, 17.\n\nFor 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.\n\nThere is no configuration with w < 4 that can kill them all.\n\n## Input\n\nThe 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 ≤ 105, 0 ≤ Q ≤ 105), where N is the number of the enemies, P is the number of small bombs, and Q is the number of large bombs.The ith line (1 ≤ i ≤ N) of the following N lines contains an integer Ai, the section where the ith enemy will be standing.\n\n## Output\n\nOutput: For each test cases print the solution of the problem on a new line.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of enemies.  \n- Let $ P, Q \\in \\mathbb{Z}_{\\geq 0} $ be the number of small and large bombs, respectively.  \n- Let $ A = (a_1, a_2, \\dots, a_N) $ be a sorted sequence of distinct enemy positions, where $ 1 \\leq a_i \\leq 10^9 $.  \n- Let $ w \\in \\mathbb{Z}^+ $ be the energy parameter.  \n\nA small bomb covers an interval of length at most $ w $, i.e., $[x, x + w - 1]$ for some $ x \\in \\mathbb{Z} $.  \nA large bomb covers an interval of length at most $ 2w $, i.e., $[x, x + 2w - 1]$ for some $ x \\in \\mathbb{Z} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown} $ (not bounded in input, but assumed finite)  \n2. $ 1 \\leq N \\leq 2000 $  \n3. $ 0 \\leq P, Q \\leq 10^5 $  \n4. $ 1 \\leq a_i \\leq 10^9 $, and $ a_i $ are sorted: $ a_1 < a_2 < \\dots < a_N $  \n\n**Objective**  \nFind the minimum $ w \\in \\mathbb{Z}^+ $ such that all enemy positions $ \\{a_1, \\dots, a_N\\} $ can be covered by at most $ P $ intervals of length $ w $ and at most $ Q $ intervals of length $ 2w $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10094J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}