촬영

호주에는 다양한 스포츠와 여러 종류의 동물처럼 흥미로운 문화가 많습니다. 당신은 브리즈번의 한 도로에서 열리는 여러 행사를 촬영하려고 합니다.

이 도로는 $10^9$개의 구간으로 나뉘어 있으며, 각 구간은 서쪽에서 동쪽으로 $1, 2, \dots, 10^9$번으로 번호가 매겨져 있습니다. 당신은 $N$개의 행사를 촬영하려 하며, $i$번째 행사는 구간 $A_i$에서 열립니다.

행사를 촬영하기 위해 작은 카메라 $P$대와 큰 카메라 $Q$대를 준비했습니다. 촬영을 위한 매개변수로 양의 정수 $w$를 하나 정할 수 있습니다. 그러면 작은 카메라는 연속한 최대 $w$개 구간을, 큰 카메라는 연속한 최대 $2w$개 구간을 촬영할 수 있습니다. 한 구간을 둘 이상의 카메라로 촬영해도 됩니다. 행사가 열리는 모든 구간을 촬영해야 합니다.

많은 인파가 예상되므로 안전을 위해 카메라의 위치를 고정해야 하며, 행사 도중에는 카메라를 옮길 수 없습니다. 매개변수 $w$가 클수록 촬영 비용이 커지므로, $w$를 가능한 한 작게 하고 싶습니다.

행사 정보와 카메라 수가 주어졌을 때, 행사가 열리는 모든 구간을 촬영할 수 있는 $w$의 최솟값을 구하는 프로그램을 작성하세요.

표준 입력으로 다음 형식의 데이터가 주어집니다.

• 첫째 줄에 공백으로 구분된 세 정수 $N$, $P$, $Q$가 주어집니다. $N$은 행사의 수, $P$는 작은 카메라의 수, $Q$는 큰 카메라의 수입니다.
• 이어지는 $N$개의 줄 중 $i$번째 줄에는 $i$번째 행사가 열리는 구간 $A_i$가 주어집니다 ($1 \le i \le N$).

행사가 열리는 모든 구간을 촬영할 수 있는 $w$의 최솟값을 정수 하나로 표준 출력에 출력하세요.

• $1 \le N \le 2000$
• $1 \le P \le 10^5$
• $1 \le Q \le 10^5$
• 모든 $1 \le i \le N$에 대해 $1 \le A_i \le 10^9$

행사가 구간 $2$, $11$, $17$에 있고 작은 카메라와 큰 카메라가 각각 한 대씩 있다고 하겠습니다. 이때 $w = 4$를 선택하면 됩니다. 작은 카메라로 $1$번부터 $4$번 구간까지(구간 $2$의 행사)를, 큰 카메라로 $11$번부터 $18$번 구간까지(구간 $11$과 $17$의 행사)를 촬영할 수 있습니다. 이보다 작은 $w$로는 불가능하므로 최솟값은 $4$입니다.