통금 시간

어떤 정보학교의 교관들이 학생들을 재운다. 집에는 방이 $n$개 있고, 각 방에는 정확히 $b$명의 학생이 자야 한다. 그러나 통금 시간에 많은 학생이 배정된 방에 있지 않다. 방은 1번부터 $n$번까지 번호가 붙은 일렬로 놓여 있다. 처음에 $i$번 방에는 $a_i$명의 학생이 있다. 모든 학생은 집 안 어딘가에 있으므로 $a_1 + a_2 + \cdots + a_n = nb$이다. 또한 집에는 $p$명의 교관이 살고 있다 ($p \le 2$).

단속 과정은 다음과 같다. 교관 한 명은 1번 방 근처에서 출발해 $n$번 방 쪽으로 이동한다. 교관이 한 명 더 있다면, 그 교관은 $n$번 방 근처에서 출발해 1번 방 쪽으로 이동한다. 각 교관은 현재 방을 처리한 뒤 다음 방으로 넘어간다. 교관이 두 명이면 두 명은 동시에 방에 들어가고 동시에 움직인다. $n$이 홀수이고 교관이 두 명이면 가운데 방은 첫 번째 교관만 처리한다. 모든 방을 처리하면 과정이 끝난다.

교관은 방을 처리할 때 방 안의 학생 수를 세고, 불을 끈 뒤 방을 잠근다. 학생 수가 $b$와 다르면 그 방 번호를 수첩에 적는다. 교관은 방에 누가 있는지는 신경 쓰지 않고 학생 수만 본다.

교관이 방 안에 있는 동안 학생들은 잠기지 않았고 처리 중이 아닌 방들 사이를 뛰어다닐 수 있다. 한 학생은 최대 $d$개의 방까지 이동할 수 있다. 즉 방 번호 차이가 $d$ 이하인 방으로 옮겨 갈 수 있다. 또한 뛴 뒤에(또는 뛰는 대신) 각 학생은 자신이 있는 방의 침대 밑에 숨을 수 있다. 숨은 학생은 교관이 세지 않는다. 한 방에 몇 명이든 동시에 숨을 수 있다.

형식으로 정리하면 다음과 같다.

• 통금이 발표된다. $i$번 방에 $a_i$명이 있다.
• 각 학생은 처음 있던 방에서 최대 $d$개 떨어진 방으로 뛰거나 제자리에 머문다. 그다음 각 학생은 선택적으로 숨을 수 있다.
• 교관이 1번 방에 들어간다 (교관이 두 명이면 $n$번 방에도 들어간다). 학생 수를 세고 방을 잠근다. 잠근 뒤에는 누구도 그 방에 들어가거나 나올 수 없다.
• 2번 방부터 $n$번 방까지 (교관이 두 명이면 2번 방부터 $n-1$번 방까지) 있는 각 학생은 현재 방에서 최대 $d$개 떨어진 방으로 뛰거나 제자리에 머문다. 각 학생은 선택적으로 숨을 수 있다.
• 교관이 다음 방으로 이동한다 (1번에서 2번 방으로, 교관이 두 명이면 $n$번에서 $n-1$번 방으로도 이동한다).
• 모든 방을 처리할 때까지 이 과정을 반복한다.

$x_i$는 $i$번째 교관이 학생 수를 $b$와 다르게 센 방의 개수이다. 학생들은 교장이 민원을 하나만 듣는다는 것을 알고 있으므로 $x_i$의 최댓값을 가능한 한 작게 만들려 한다. 학생들이 최적 전략을 쓸 때 이 값을 구하라.

첫 줄에 네 정수 $p$, $n$, $d$, $b$가 주어진다 ($1 \le p \le 2$, $2 \le n \le 100\,000$, $1 \le d \le n - 1$, $1 \le b \le 10\,000$). 각각 교관의 수, 방의 수, 학생이 뛸 수 있는 거리, 방마다 정해진 학생 수이다.

둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)이 주어진다. $a_i$는 통금이 발표되기 전 $i$번 방의 학생 수이다.

$a_1 + a_2 + \cdots + a_n = nb$가 성립함이 보장된다.

학생들이 최적 전략을 쓸 때 $x_i$의 최댓값이 가질 수 있는 최솟값을 정수 하나로 출력한다.

첫 번째 예제에서 학생들은 교관이 1번 방에 들어오기 전에 자기 방에 도달할 만큼 빠르게 뛸 수 있다. 따라서 답은 0이다.

두 번째 예제에서 교관은 적어도 한 방을 수첩에 적는다. 최적 전략 중 하나는 다음과 같다. 교관이 1번 방에 들어오기 전에 5번 방에 있던 학생 10명이 2번 방으로, 10명이 3번 방으로, 10명이 4번 방으로 뛴다. 그다음 2, 3, 4번 방에서 학생 한 명씩 숨고, 5번 방에서는 두 명이 숨는다. 이후 학생들은 아무것도 하지 않는다. 이렇게 하면 1번 방만 수첩에 적힌다.

세 번째 예제에서 앞의 세 방은 첫 번째 교관이, 뒤의 두 방은 두 번째 교관이 처리한다. 최적 전략 중 하나는 다음과 같다. 먼저 5번 방의 학생 세 명이 4번 방으로 뛴다. 다음 단계에서 그중 두 명이 3번 방으로 뛰고, 그중 한 명이 숨는다. 첫 번째 교관은 2번 방을 적고, 두 번째 교관은 아무것도 적지 않는다.

네 번째 예제에서 최적 전략 중 하나는 다음과 같다. 먼저 1번 방의 학생이 모두 숨고, 2번 방의 학생이 모두 3번 방으로 뛴다. 다음 단계에서 3번 방의 학생 한 명이 4번 방으로 뛰고, 5명이 숨는다. 첫 번째 교관은 1번과 2번 방을, 두 번째 교관은 5번과 6번 방을 적는다.