406145: GYM102279 C Countering Terrorists

Has someone ever said Vietnam is out of the effect of terrorism ?

Indeed, S_e_o, the current prime minister of Vietnam, is so proud that he has turned Vietnam into the safest area in the world, with no terrorism, unlike the U.S or France. However, he is not aware of a conspiracy to terrorize Vietnam by launching a series of Bomb right on Tran Duy Hung street, Hanoi.

However, a secret agent team has informed S_e_o about the terrorists' plan.

Tran Duy Hung street could be modeled as a segment $$$[1, 10^{9}]$$$ in the Ox axis. There are $$$n (1\le n\le 2000)$$$ bombs known to be located on distinct integer coordinates on the street. The government has only $$$P$$$ type-1 tools and $$$Q (0\le P, Q\le 10^{5})$$$ type-2 tools that could eliminate bombs. The difference between to type is that type-1 destroy bombs in a subsegment with length $$$w$$$, while type-2 could destroy in a subsegment of $$$2w$$$. However, each tool could only be used once.

At this time, HCW is going on, and HCW Organizing Committee just wonders the minimum $$$w (1\le w)$$$ that allows S_e_o to destroy the terrorists' plan. Now it turns out to be your duty to find the answer. It is guaranteed that S_e_o could always destroy the terrorism conspiracy to save Hanoi and Vietnam.

Line 1: 3 numbers $$$n,P, Q$$$

Line 2... $$$ n+1$$$: Each line contains a number $$$x$$$ indicates the location of a bomb.

Print a single number which is the answer.

3 1 1
2
11
17

4