Watching

Australia has many fascinating aspects of culture, from a wide range of sports to all sorts of animals. You want to watch several events held along a single road in Brisbane.

The road is divided into $10^9$ sections, numbered $1, 2, \dots, 10^9$ from west to east. You want to watch $N$ events; the $i$-th event is held in section $A_i$.

To photograph the events you have prepared $P$ small cameras and $Q$ large cameras. You may choose one positive integer $w$ as a shared parameter. A small camera can then photograph at most $w$ consecutive sections, and a large camera can photograph at most $2w$ consecutive sections. A single section may be photographed by more than one camera. You must photograph every section in which an event is held.

Because a large crowd is expected, the cameras must be fixed in place for safety and cannot be moved during the events. The larger the parameter $w$ is, the higher the cost, so you want $w$ to be as small as possible.

Write a program that, given the events and the number of cameras, determines the minimum value of $w$ for which every event section can be photographed.

The input is given on standard input in the following format.

• The first line contains three space-separated integers $N$, $P$, and $Q$: the number of events, the number of small cameras, and the number of large cameras.
• Each of the next $N$ lines contains one integer $A_i$, the section in which the $i$-th event is held ($1 \le i \le N$).

Print a single integer: the minimum value of $w$ for which every event section can be photographed.

• $1 \le N \le 2000$
• $1 \le P \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le A_i \le 10^9$ for every $1 \le i \le N$

As an illustration, suppose there are events in sections $2$, $11$, and $17$ with one small and one large camera. Choosing $w = 4$ works: a small camera can cover sections $1$ through $4$ (photographing the event in section $2$), and a large camera can cover sections $11$ through $18$ (photographing the events in sections $11$ and $17$). No smaller $w$ is possible, so the minimum is $4$.