A8654 | Xor

John Doe has four arrays: $a$ , $b$ , $k$ , and $p$ . Each array consists of $n$ integers. Elements of all arrays are indexed starting from $1$ . Array $p$ is a permutation of integers $1$ to $n$ .

John invented a game for his friends and himself. Initially a player is given array $a$ . The player must consecutively execute exactly $u$ operations on $a$ . You are permitted to execute the following operations:

- Operation 1: For each  change $a_{i}$ into . Expression  means applying the operation of a bitwise xor to numbers $x$ and $y$ . The given operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "^", in Pascal — as "xor".
- Operation 2: For each  change $a_{i}$ into $a_{pi}+r$ . When this operation is executed, all changes are made at the same time.

After all $u$ operations are applied, the number of points the player gets is determined by the formula .

John wants to find out what maximum number of points a player can win in his game. Help him.

The first line contains space-separated integers $n$ , $u$ and $r$ ( $1<=n,u<=30$ , $0<=r<=100$ ) — the number of elements in each array, the number of operations and the number that describes one of the operations.

Each of the next four lines contains $n$ space-separated integers — arrays $a$ , $b$ , $k$ , $p$ . The first line has array $a$ , the second line has array $b$ , the third line has array $k$ and the fourth one has array $p$ .

It is guaranteed that elements of arrays $a$ and $b$ are positive and do not exceed $10^{4}$ $(1<=a_{i},b_{i}<=10^{4})$ , elements of array $k$ do not exceed $10^{4}$ in the absolute value $(|k|<=10^{4})$ and $p$ is a permutation of numbers from $1$ to $n$ .

On a single line print number $s$ — the maximum number of points that a player can win in John's game.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.