P15402 [NOISG 2026 Prelim] Digits（暂无数据）

杰登是一个痴迷于数字的数学极客！他最爱的数字是一个 $m$ 位的字符串 $x$。吉夫给了他另外 $n$ 个 $m$ 位的字符串 $v[1], v[2], \ldots, v[n]$。这些字符串（包括 $x$）中的所有数字范围都是 $0$ 到 $k-1$，其中 $k$ 是一个给定的整数（$2 \le k \le 10$）。用 $v[i][j]$ 表示 $v[i]$ 从左起的第 $j$ 位数字。 由于杰登非常喜爱他的最爱数字 $x$，他希望使用数字转换机将吉夫给他的所有 $n$ 个数字都转换成数字 $x$。对 $v[i]$ 的一次操作如下： - 选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le m$。 - 对于每个 $l \le j \le r$，将 $v[i][j]$ 的值设置为 $(v[i][j] + a[j]) \mod k$。 其中 $a$ 是一个给定的长度为 $m$ 的数组。$p \bmod q$ 表示 $p$ 除以 $q$ 的余数（例如，$5 \bmod 2 = 1$）。该操作的成本为 $c[l] + c[r]$ 美元（特别地，如果 $l = r$，成本为 $c[l] + c[l]$），其中 $c$ 是一个给定的长度为 $m$ 的数组。更多细节请参考样例测试用例。 对于每个 $v[i]$，帮助杰登 **独立地** 解决以下问题： - 使用任意次操作将 $v[i]$ 转换为 $x$ 所需的最小总成本（以美元计）是多少？ 如果无法将 $v[i]$ 转换为 $x$，则输出 $-1$。

你的程序必须从标准输入中读取数据。 输入的第一行包含三个以空格分隔的整数 $n$、$m$ 和 $k$。 输入的第二行包含 $m$ 个以空格分隔的整数 $a[1], a[2], \ldots, a[m]$。 输入的第三行包含 $m$ 个以空格分隔的整数 $c[1], c[2], \ldots, c[m]$。 输入的第四行包含一个整数 $x$。 接下来的 $n$ 行，每行包含一个整数。第 $i$ 行包含 $v[i]$。

你的程序必须输出到标准输出。 输出应包含 $n$ 行，每行一个整数。第 $i$ 行应包含将 $v[i]$ 转换为 $x$ 所需的最小总成本。如果不可能，则输出 $-1$。

#### 样例测试用例 1 解释 杰登的最爱数字是 $x = 676$。 考虑 $v[1] = 356$。以下 3 次操作的序列可以将 356 转换为 676： $$ \underline{356} \xrightarrow{l=1,\ r=2} \underline{476} \xrightarrow{l=1,\ r=1} \underline{576} \xrightarrow{l=1,\ r=1} \underline{676} $$ 1. $l = 1, r = 2$：第 1 位和第 2 位分别变为 $(3 + 1) \mod 8 = 4$ 和 $(5 + 2) \mod 8 = 7$。成本为 $c[1] + c[2] = 3 + 1 = 4$ 美元。 2. $l = 1, r = 1$：第 1 位变为 $(4 + 1) \mod 8 = 5$。成本为 $c[1] + c[1] = 3 + 3 = 6$ 美元。 3. $l = 1, r = 1$：第 1 位变为 $(5 + 1) \mod 8 = 6$。成本为 6 美元。 三次操作的总成本为 $4 + 6 + 6 = 16$ 美元。可以证明不存在其他总成本更低的操作序列。 对于 $v[3] = 676$，无需进行任何操作，因为该数字已经等于 $x$。因此，最小总成本为 0 美元。 对于 $v[4] = 767$，可以证明不存在任何操作序列能将 767 转换为 676。因此，输出 $-1$。 #### 子任务 对于所有测试用例，输入均满足以下范围： - $1 \le n \le 200000$ - $1 \le m \le 5$ - $2 \le k \le 10$ - 对于所有 $1 \le i \le m$，$1 \le a[i] \le k - 1$ - 对于所有 $1 \le i \le m$，$1 \le c[i] \le 10^9$ - $x, v[1], v[2], \ldots, v[n]$ 均为 $m$ 位字符串，每个数字的取值范围为 $0$ 到 $k - 1$（包含端点）。它们可能包含前导零。 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分值 | 附加约束 | |:-:|:-:|:-:| | 0 | 0 | 样例测试用例 | | 1 | 5 | $m = 1$ 且对于所有 $1 \le i \le m$，有 $a[i] = 1$ | | 2 | 13 | $m = 2$ 且对于所有 $1 \le i \le m$，有 $a[i] = 1$ | | 3 | 10 | $k = 2$ 且 $c[1] = c[2] = \cdots = c[m]$ | | 4 | 16 | $c[1] = c[2] = \cdots = c[m]$ | | 5 | 24 | $n \le 20$ | | 6 | 32 | 无额外约束 | 翻译由 DeepSeek 完成