题目描述

geven 终于把题出完了，于是他开始玩邦邦。

他把 $n$ 个少女拉出来站成环形，其中第 $i$ 个少女有能力值 $A_i$。（少女从 $0$ 开始编号，且 $0$ 号少女和 $n-1$ 号少女相邻。）少女们有能力值上限 $M$，且她们的能力值会随时随地对 $M$ 取模。

他还有若干星光魔方，他可以消耗一个星光魔方，并选择连续的 $k$ 个少女，做以下操作之一：

• 将 $k$ 个少女的能力值全部 $+1$。
• 将 $k$ 个少女的能力值全部 $-1$。

如果你理解了上述内容，你可以知道，若 $A_i = 0$，将它 $-1$ 会让它变成 $M-1$。同理，若 $A_i = M-1$，将它 $+1$ 会让它变成 $0$。

现在他想让所有少女的能力值均变成 $V$，请你告诉他他最少需要的星光魔方数量，或者告诉他这不可能。

输入格式

第一行四个整数 $n,M,k,V$，含义如上。

第二行 $n$ 个整数，代表 $A$ 数组。

输出格式

一行一个整数，表示答案。

若无解，输出 -1。

样例输入 #1

5 5 3 2
1 3 3 0 4

样例输出 #1

6

样例输入 #2

10 10 5 5
0 5 6 3 5 3 5 1 5 6

样例输出 #2

-1

样例输入 #3

10 10 2 0
0 0 0 0 0 0 1 0 0 0

样例输出 #3

-1

样例输入 #4

10 10 2 0
0 0 0 0 0 0 0 0 0 0

样例输出 #4

0

样例输入输出 #5

见下发文件 ex_bandream5.in/.out，该样例满足子任务1,2,3的限制。

样例输入输出 #6

见下发文件 ex_bandream6.in/.out，该样例满足子任务4的限制。

样例输入输出 #7

见下发文件 ex_bandream7.in/.out，该样例满足子任务5的限制。

数据范围

本题开启子任务评测。

所有测试点均满足 $1\leq n,M\leq 10^6,nM\leq 2\times 10^6,1\leq k < n,0\leq A_i,V < M$ 。

各子任务的约束条件如下：