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

도로는 동서로 한 줄로 늘어선 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).

#5018 upload 100 done 29 how_to_reg 27 call_split Subtask

구경하기 timer 1s memory 512MB

#5018
Subtask

구경하기 1s 512MB