eolymp
bolt
Try our new interface for solving problems
Problems

Fire extinguishing robot

Fire extinguishing robot

Time limit 1 second
Memory limit 128 MiB

During fires in Australia, the plot of land where the fire occurred was represented as a straight line, divided into 10^9 parts, numbered from 1 to 10^9. 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 data

First line contains three numbers n (1n2000) , p and q (0p,q10^5, p + q > 0) . Each of the next n lines contains one integer x[i] (1x[i]10^9) - the coordinates of the burning parts of the plot.

Output data

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

Examples

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