P15402 [NOISG 2026 Prelim] Digits

Jayden is a math nerd who is obsessed with numbers! His favourite number is an $m$-digit string $x$. Ziv gives him $n$ other $m$-digit strings $v[1], v[2], \ldots, v[n]$. All digits in these strings (including $x$) range from 0 to $k-1$, where $k$ is a given integer ($2 \le k \le 10$). Let $v[i][j]$ denote the $j$-th digit of $v[i]$ from the left. As Jayden loves his favorite number $x$ so much, he wishes to turn all the $n$ numbers that Ziv gave him into the number $x$ using a number transformation machine. An operation on $v[i]$ works as follows: - Choose two integers $l$ and $r$ where $1 \le l \le r \le m$. - For every $l \le j \le r$, set the value of $v[i][j]$ to $(v[i][j] + a[j]) \mod k$. $a$ is a given array of length $m$. $p \mod q$ denotes the remainder of dividing $p$ by $q$ (for example, $5 \mod 2 = 1$). The cost of this operation is $c[l] + c[r]$ dollars (in particular, if $l = r$, the cost is $c[l] + c[l]$), where $c$ is a given array of length $m$. Refer to the sample test cases for more details. For each $v[i]$, help Jayden solve the following problem **independently**: - What is the minimum total cost needed (in dollars) to transform $v[i]$ into the number $x$ using any number of operations? If it is impossible to transform $v[i]$ into $x$, output $-1$ instead.

Your program must read from standard input. The first line of input contains three space-separated integers $n$, $m$, and $k$. The second line of input contains $m$ space-separated integers $a[1], a[2], \ldots, a[m]$. The third line of input contains $m$ space-separated integers, $c[1], c[2], \ldots, c[m]$. The fourth line of input contains one integer $x$. The next $n$ lines of input each contain one integer. The $i$-th of these lines contains $v[i]$.

Your program must print to standard output. The output should contain $n$ lines, each containing one integer. The $i$-th of these lines should contain the minimum total cost needed to transform $v[i]$ into $x$. If this is impossible, output $-1$ instead.

### Sample Test Case 1 Explanation Jayden’s favourite number is $x = 676$. Consider $v[1] = 356$. The following sequence of 3 operations can transform 356 into 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$: The 1-st and 2-nd digits become $(3 + 1) \mod 8 = 4$ and $(5 + 2) \mod 8 = 7$ respectively. This costs $c[1] + c[2] = 3 + 1 = 4$ dollars. 2. $l = 1, r = 1$: The 1-st digit becomes $(4 + 1) \mod 8 = 5$. This costs $c[1] + c[1] = 3 + 3 = 6$ dollars. 3. $l = 1, r = 1$: The 1-st digit becomes $(5 + 1) \mod 8 = 6$. This costs 6 dollars. The total cost of the three operations is $4 + 6 + 6 = 16$ dollars. It can be shown that there is no other sequence of operations that incurs a lower total cost. For $v[3] = 676$, no operations have to be made as the number is already equal to $x$. Hence, the minimum total cost is 0 dollars. For $v[4] = 767$, it can be shown that there is no sequence of operations that can transform 767 into 676. Hence, output $-1$. ### Subtasks For all test cases, the input will satisfy the following bounds: - $1 \le n \le 200000$ - $1 \le m \le 5$ - $2 \le k \le 10$ - $1 \le a[i] \le k - 1$ for all $1 \le i \le m$ - $1 \le c[i] \le 10^9$ for all $1 \le i \le m$ - $x, v[1], v[2], \ldots, v[n]$ are all $m$-digit strings, where each digit ranges from 0 to $k - 1$ inclusive. They may contain leading zeros. Your program will be tested on input instances that satisfy the following restrictions: | Subtask | Score | Additional Constraints | |:-:|:-:|:-:| | 0 | 0 | Sample test cases | | 1 | 5 | $m = 1$ and $a[i] = 1$ for all $1 \le i \le m$ | | 2 | 13 | $m = 2$ and $a[i] = 1$ for all $1 \le i \le m$ | | 3 | 10 | $k = 2$ and $c[1] = c[2] = \cdots = c[m]$ | | 4 | 16 | $c[1] = c[2] = \cdots = c[m]$ | | 5 | 24 | $n \le 20$ | | 6 | 32 | No additional constraints |