구경하기 Batch 컴파일 명령

다양한 동물들과 스포츠와 같은 호주의 문화는 상당히 흥미롭습니다. 당신은 Brisbane의 한 도로에서 개최되는 다양한 행사들을 지켜보려고 합니다.

도로는 $1 000 000 000$개의 구역으로 나뉘어 있고, 각 구역에는 왼쪽에서부터 차례대로 ($1, 2, 3, ..., 1 000 000 000$) 번호가 붙어 있습니다. 당신은 $N$개의 행사를 보고 싶어 합니다. 이 중 $i$번째 행사는 $A_i$번 구역에서 실시될 예정입니다.

당신은 행사들을 구경하기 위해 $P$개의 작은 카메라와 $Q$개의 큰 카메라를 준비했습니다. 행사를 촬영하기 위해서, 당신은 카메라의 시야를 나타내는 양의 정수 $w$를 결정할 수 있습니다. 이제 작은 카메라 하나는 최대 $w$개, 큰 카메라 하나는 최대 $2w$개의 연속적인 구획을 촬영할 수 있습니다. 한 구역이 여러 개의 카메라로 촬영되더라도 상관 없습니다.

당신은 행사가 개최되는 모든 구역을 촬영하고 싶습니다. 많은 사람들이 행사에 참가할 것으로 예상되므로, 안전을 위해 당신은 모든 카메라를 고정하여 행사가 진행되는 동안 움직이게 해서는 안 됩니다. 시야 $w$가 커질수록 더 많은 돈이 드므로, 당신은 $w$의 값을 최소화하고자 합니다.

해야 할 일

행사가 개최되는 구역의 정보와 카메라의 수가 주어질 때, 당신이 모든 행사를 촬영할 수 있도록 하는 카메라의 시야 $w$의 최솟값을 구하는 프로그램을 작성하세요.

입력

표준 입력에서 아래 정보를 읽으세요:

• 첫째 줄에 행사의 수 $N$, 작은 카메라의 수 $P$, 큰 카메라의 수 $Q$가 공백을 사이로 두고 주어집니다.
• $N$개의 줄이 더 주어지는데, 이 중 $i$ ($1 \le i \le N$)번째 줄에 $i$번 행사가 진행될 구역의 위치 $A_i$가 주어집니다.

출력

표준 출력에 모든 행사를 촬영할 수 있는 최소한의 카메라의 시야 $w$를 출력하세요.

제약 조건

모든 입력 데이터는 아래 조건을 만족합니다.

• $1 \le N \le 2 000.$
• $1 \le P \le 100 000.$
• $1 \le Q \le 100 000.$
• $1 \le A_i \le 1 000 000 000.$ ($1 \le i \le N$)

서브태스크

서브태스크 1 (50점)

• $N \le 100$임이 보장됩니다.

서브태스크 2 (50점)

별다른 제약 조건이 없습니다.

입력과 출력의 예

예제 1

입력

3 1 1
2
11
17

출력

4

예제 2

입력

13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75

출력

9

첫 번째 예제에서, $w$를 4로 정하면 모든 행사를 촬영할 수 있습니다. 작은 카메라 한 대로 1번부터 4번 구역을 촬영하고, 큰 카메라 한 대로 11번부터 18번 구역을 촬영하면 됩니다.