문제
호주의 문화는 다양한 동물들과 다양한 스포츠로 인하여 상당히 흥미롭습니다. 당신은 Brisbane의 한 도로에서 개최되는 다양한 행사들을 지켜보려고 합니다.
도로는 1,000,000,000개의 구역으로 나뉘어 있고, 각 구역에는 왼쪽에서부터 차례대로 (1,2,3,...,1,000,000,000) 번호가 붙어 있습니다. 당신은 N개의 행사를 보고 싶어 합니다. 이 중 i번째 행사는 Ai번 구역에서 실시될 예정입니다.
당신은 행사들을 구경하기 위해 P개의 작은 카메라와 Q개의 큰 카메라를 준비했습니다. 행사를 촬영하기 위해서, 당신은 카메라의 시야를 나타내는 양의 정수 w를 결정할 수 있습니다. 이제 작은 카메라 하나는 최대 w개, 큰 카메라 하나는 최대 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)
서브태스크 1 (50점)
N≤100임이 보장됩니다.
서브태스크 2 (50점)
별다른 제약 조건이 없습니다.
입력
첫째 줄에 행사의 수 N, 작은 카메라의 수 P, 큰 카메라의 수 Q가 공백을 사이로 두고 주어집니다.
N개의 줄이 더 주어지는데, 이 중 i (1≤i≤N)번째 줄에 i번 행사가 진행될 구역의 위치 Ai가 주어집니다.
출력
표준 출력에 모든 행사를 촬영할 수 있는 최소한의 카메라의 시야 w를 출력하세요.
예제1
311
2
11
17
4
예제2
1332
33
66
99
10
83
68
19
83
93
53
15
66
75
9