XOR Expedition

There are $2^{N}$ stations, numbered $0, 1, \ldots, 2^{N}-1$. Each station $x$ has an integer value $V_{x}$.

A traveler starts at station $S$ and performs exactly $K$ operations. In one operation, the traveler chooses one of the following actions:

• Remain at the current station.
• Choose an integer $j$ with $1 \le j \le M$ and move from current station $x$ to station $x \oplus D_{j}$.

Here, $\oplus$ denotes the bitwise XOR operation.

After each operation, if the traveler is at station $x$, they earn $V_{x}$ points.

Determine the maximum possible total number of points earned during the $K$ operations.

The first line contains three integers $N$, $M$, and $K$.

The second line contains an integer $S$.

The third line contains integers $D_1,D_2,\ldots,D_M$.

The fourth line contains integers $V_{0},V_{1},\ldots,V_{2^{N}-1}$.

• $1 \le N, M \le 12$
• $1 \le K \le 10^{18}$
• $0 \le S < 2^{N}$
• $1 \le D_{j} < 2^{N}$
• The integers $D_1,D_2,\ldots,D_M$ are pairwise distinct.
• $1 \le V_{x} \le 10^{9}$

Print the maximum possible total number of points.

Note that the answer may not fit in a signed 64-bit integer.

It can be proven that arbitrary-precision integers that can represent a signed 128-bit integer, such as Python's int, Java's BigInteger, or C++ __int128, is sufficient in this problem.