CF1740I Arranging Crystal Balls

在 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$，他可以进行零次或多次操作。每次操作如下： 1. 选择恰好 $k$ 个连续的雕像。也就是说，选择编号为 $p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n$ 的雕像，其中 $p$ 是任意选择的起始编号。 2. 对所选的所有雕像，执行以下两种操作之一： - 将所有选中雕像的 $a_i$ 变为 $(a_i+1) \bmod m$。 - 将所有选中雕像的 $a_i$ 变为 $(a_i-1) \bmod m$。 请你帮助 Pak Chanek 求出打开宝箱所需的最少操作次数。如果无法通过若干次操作使所有 $a_i=0$，输出 $-1$。

第一行包含三个整数 $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$。

在第一个样例中，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]$。 由 ChatGPT 4.1 翻译