e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

2019-2020 Azerbaijan Finals, June 17

Fire extinguishing robot

During fires in Australia, the plot of land where the fire occurred was represented as a straight line, divided into 109 parts, numbered from 1 to 109. At the moment, fire is occurring on n parts of the site. In order to extinguish the fires, an expert on forest fires, Murad, was invited.

Murad is going to use his fire extinguishing robot. He has p small and q large robots. All robots work according to the same system. The system has a fire range - always an integer. If the fire range is w, then a small robot can extinguish w consecutive parts from the last stop, while a large robot 2w parts. No robot can move or change its location in the process of extinguishing a fire. Obviously, the larger the fire range, the more electricity the robots spend. Therefore, Murad wants to put out the fire with the smallest possible range of fire. Help Murad and calculate the minimum possible range of fire at which you can put out the fire.

Input

First line contains three numbers n (1n2000) , p and q (0p,q105, p + q > 0) . Each of the next n lines contains one integer xi (1xi109) - the coordinates of the burning parts of the plot.

Output

Print the smallest possible range of fire at which a fire can be extinguished.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 1 1
2
11
17
Output example #1
4
Input example #2
13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75
Output example #2
9
Source 2019-2020 Azerbaijan Final, June 17