题目描述

译自 JOI Open 2013 T3 「ウォッチング / Watching」

澳大利亚有很多有趣的文化，比如各种各样的运动和动物。你想在布里斯班的一条道路上观察一些举行的活动。

这条道路由东西方向排成一行的 $10^9$ 个格子组成，从西到东依次编号为 $1$ 到 $10^9$。你想观察的活动有 $N$ 个，第 $i$ 个活动在格子 $A_{i}$ 举行。

为了观察活动，你有 $P$ 台小型相机和 $Q$ 台大型相机。你可以指定一个正整数 $w$ 作为拍摄的参数。一台小型相机可以拍摄一个连续的最多 $w$ 个格子，一台大型相机可以拍摄一个连续的最多 $2w$ 个格子。同一个格子可以被多台相机拍摄，但你想拍摄所有举行活动的格子。另外，由于预计会有很多参与者，为了安全起见，相机的位置是固定的，活动期间不能移动相机。参数 $w$ 越大，拍摄的费用就越高，所以你想让 $w$ 的值尽可能小。

给定活动的信息和相机的数量，编写一个程序，求出拍摄所有举行活动的格子所需的 $w$ 的最小值。

输入格式

第一行包含三个用空格分隔的整数 $N, P, Q$，分别表示活动的个数，小型相机的数量，大型相机的数量。

接下来的 $N$ 行，每行有一个整数 $A_{i}$，表示第 $i$ 个活动在格子 $A_{i}$ 举行。

输出格式

输出一行，表示拍摄所有举行活动的格子所需的 $w$ 的最小值。

3 1 1
2
11
17

4

13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75

9

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 2000$
• $1 \leq P \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_{i} \leq 10^9\ (1 \leq i \leq N)$

详细子任务附加限制及分值如下表所示。