在 Compfestnesia 的世界中,Pak Chanek 发现了一个秘密的地下地牢。里面有一个宝箱,周围环绕着以圆形方式排列的 $$$n$$$ 雕像。雕像编号从 $$$0$$$ 到 $$$n-1$$$,其中雕像 $$$i$$$ 位于雕像 $$$i+1$$$ 的左侧,雕像 $$$n-1$$$ 位于雕像 $$$0$$$ 的左侧。
Pak Chanek 观察到每个雕像都拿着一个水晶球,水晶球上的整数介于 $$$0$$$ 和 $$$m-1$$$ 之间(含)。假设雕像 $$$i$$$ 水晶球中的整数是 $$$a_i$$$。
地下城规定,水晶球中的每个整数必须为 $$$0$$$ 才能打开宝箱。为了实现这一点,Pak Chanek 被赋予一个整数 $$$k$$$,并且他可以执行零个或多个操作。在一次操作中,Pak Chanek 执行以下操作:
1. 准确选择 $$$k$$$ 连续雕像。换句话说,为某个选定的索引 $$$p$$$ 选择雕像 $$$p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n$$$。
2. 执行以下操作之一: 对于所有选定的雕像,将其 $$$a_i$$$ 值更改为 $$$(a_i+1) \bmod m$$$。 对于所有选定的雕像,将其 $$$a_i$$$ 值更改为 $$$(a_i-1) \bmod m$$$。
帮助 Pak Chanek 找到打开宝箱的最少可能操作次数。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \leq n,m \leq 10^6$$$, $$$nm \leq 2 \cdot 10^6$$$, $$$1 \leq k < n$$$) — 雕像的数量,晶体中整数的界限球,以及一次操作中可以操作的雕像数量。
第二行包含 $$$n$$$ 整数 $$$a_0,a_1,\ldots,a_{n-1}$$$ ($$$0 \leq a_i < m$$$) — 水晶球中的整数。
输出
如果可以执行零个或多个运算使得 $$$a_0=a_1=\ldots=a_{n-1}=0$$$,则输出所需的最少运算数。否则,输出$$$-1$$$。
示例
输入 #1
5 9 3 8 1 4 5 0
输出 #1
7
输入 #2
4 4 2 1 0 0 0
输出 #2
-1
输入 #3
5 5 2 1 0 0 0 0
输出 #3
10
注意
在第一个示例中,Pak Chanek 可以执行以下操作:
1. 对雕像 $$$1$$$、$$$2$$$ 和 $$$3$$$ 执行 $$$a_i := (a_i-1) \bmod m$$$ 操作 $$$3$$$ 次。现在$$$a=[8,7,1,2,0]$$$。
2. 对雕像 $$$3$$$、$$$4$$$ 和 $$$0$$$ 执行 $$$a_i := (a_i-1) \bmod m$$$ 操作 $$$1$$$ 时间。现在$$$a=[7,7,1,1,8]$$$。
3. 对雕像 $$$4$$$、$$$0$$$ 和 $$$1$$$ 执行 $$$a_i := (a_i+1) \bmod m$$$ 操作 $$$2$$$ 次。现在$$$a=[0,0,1,1,1]$$$。
4. 对雕像 $$$2$$$、$$$3$$$ 和 $$$4$$$ 执行 $$$a_i := (a_i-1) \bmod m$$$ 操作 $$$1$$$ 时间。现在$$$a=[0,0,0,0,0]$$$。