33918번 - 맛있는 스콘 만들기

도현이는 SCON 참가자들에게 나눠줄 간식으로 스콘을 만들기로 했다.

매 시각마다 스콘이 가장 맛있게 구워지는 최적의 온도가 존재한다는 사실을 알고 있는 도현이는 시각 $0$부터 시작하여 시각 $N-1$까지 오븐의 온도를 총 $N$번 조절하여 스콘을 굽기로 했다.

스콘을 만드는 데 사용할 오븐은 $1$부터 $M$까지의 정수 온도로 조절이 가능하다. 각 시각마다 한 번만 오븐의 온도를 조절할 수 있는데, 시각 $0$에서는 자유롭게 오븐의 온도를 조절할 수 있지만, 다른 시각에서는 기존 온도에서 $C$의 정수 배만큼만 온도를 높이거나 낮출 수 있다. 또, 한 번에 $D$를 초과해서 온도를 높이거나 낮출 수 없다. 예를 들어, 시각 $t$에서 오븐의 온도를 $182$로 조절했고, $C=5,D=10$일 경우, 시각 $t+1$에서 조절 가능한 온도는 $172,177,182,187,192$뿐이다.

시각 $t$에서의 최적의 온도를 $b_t$, 시각 $t$에서 조절한 오븐의 온도를 $k_t$라고 하면 시각 $t+1$에서 스콘의 맛은 $M-|b_t-k_t|$만큼 증가한다.

시각 $0$부터 시각 $N-1$까지의 최적의 온도가 주어졌을 때, 시각 $N$에 완성되는 스콘의 맛의 최댓값을 구해보자. 처음 스콘을 오븐에 넣었을 때의 시각은 $0$이며, 스콘의 맛은 $0$이다. 모든 시각은 정수 시각만 고려한다.

첫째 줄에 네 정수 $N,M,C,D$가 공백으로 구분되어 주어진다.

둘째 줄에 각 시각의 최적의 온도를 의미하는 $N$개의 정수 $b_0,b_1,...,b_{N-1}$이 주어진다.

시각 $N$에 완성되는 스콘의 맛의 최댓값을 출력한다.

• $1\leq N\leq 200$
• $1\leq M\leq 25\, 000$
• $1\leq C\leq D\leq M$
• $D$는 $C$의 배수이다.
• $1\le b_i\le M$ ($0\le i\le N-1$)
• 입력으로 주어지는 수는 모두 정수이다.