Page not loading? Try clicking here.
Placeholder

#5018
Subtask

구경하기 1s 512MB

Problems

호주에는 다양한 스포츠와 동물 등 흥미로운 문화가 많이 있습니다.
당신은 브리즈번의 한 도로에서 열리는 이벤트를 관찰하기로 했습니다.

도로는 동서로 한 줄로 늘어선 1\ 000\ 000\ 000개의 칸으로 이루어져 있으며, 가장 서쪽 칸부터 순서대로 1, 2, ..., 1\ 000\ 000\ 000의 번호가 붙어 있습니다. 당신이 관찰하고 싶은 이벤트는 N개가 있으며, i번째 이벤트는 A_i 칸에서 열립니다.

이벤트 관찰을 위해 소형 카메라 P대와 대형 카메라 Q대가 준비되어 있습니다.
촬영용 매개변수로 양의 정수 w를 지정할 수 있습니다.
소형 카메라 1대는 연속된 최대 w개의 칸을,
대형 카메라 1대는 연속된 최대 2w개의 칸을 촬영할 수 있습니다.
같은 칸을 여러 카메라가 촬영해도 되지만, 이벤트가 열리는 모든 칸을 촬영해야 합니다.
또한, 이벤트에는 많은 참가자가 올 것으로 예상되므로 안전을 위해 카메라 위치는 고정하며, 이벤트 중에 카메라를 움직일 수 없습니다.
매개변수 w가 클수록 촬영 비용이 비싸지므로, 당신은 w의 값을 최소화하고 싶습니다.

이벤트 정보와 카메라 수가 주어졌을 때, 이벤트가 열리는 모든 칸을 촬영하기 위한 w의 최솟값을 구하는 프로그램을 작성하세요.

  • 1 ≤ N ≤ 2\ 000.

  • 1 ≤ P ≤ 100\,000.

  • 1 ≤ Q ≤ 100\ 000.

  • 1 ≤ Ai ≤ 1\ 000\ 000\ 000 (1 ≤ i ≤ N).


Input

첫 번째 줄에는 정수 N, P, Q가 공백으로 구분되어 주어지며, 각각 이벤트의 개수, 소형 카메라의 대수, 대형 카메라의 대수를 나타냅니다.

이어지는 N개의 줄 중 i번째 줄(1 ≤ i ≤ N)에는 정수 A_i가 주어지며, i번째 이벤트가 A_i칸에서 열리는 것을 나타냅니다.


Output

표준 출력에 이벤트가 열리는 모든 칸을 촬영하기 위한 w의 최솟값을 한 줄로 출력하세요.


Example #1

3 1 1

2

11

17
4

w=4로 설정하면 이벤트가 열리는 모든 칸을 촬영할 수 있습니다. 예를 들어, 소형 카메라 1대로 1번 칸부터 3번 칸까지 촬영하고, 대형 카메라 1대로 11번 칸부터 18번 칸까지 촬영하면 됩니다.


Example #2

13 3 2

33

66

99

10

83

68

19

83

93

53

15

66

75
9

Source

JOI Open Contest 2013
You must sign in to write code.