Xor

题意翻译

### 题意翻译 给定四个长度为 $n$，下标从 $1$ 到 $n$ 的数组 $a$，$b$，$k$，$p$，保证 $p_1, p_2,\cdots, p_n$ 是 $1, 2,\cdots, n$ 的一个排列。 你要对数组 $a$ 进行恰好 $u$ 次操作，每次可以在以下两种操作中选择一种： 1. 对所有 $i = 1, 2,\cdots, n$，将 $a_i$ 修改为 $a_i \oplus b_i$。($\oplus$ 表示异或) 1. 对所有 $i = 1, 2,\cdots, n$，将 $a_i$ 修改为 $a_{p_i} + r$。 请问，$u$ 次操作之后 $\sum \limits _{i=1}^n a_i \times k_i$ 最大为多少。 ### 输入格式 第一行三个正整数 $n, u, r$。 第二行 $n$ 个正整数表示 $a$。 第三行 $n$ 个正整数表示 $b$。 第四行 $n$ 个正整数表示 $k$。 第五行 $n$ 个正整数表示 $p$。 ### 输出格式 只有一行，$\sum \limits _{i=1}^n a_i \times k_i$ 的最大值。 ### 数据规模 $1 \le n,u \le 30$。 $0 \le r \le 100$。 $0 \le a_i,b_i \le 10^4$。

题目描述

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.

输入输出样例

输入样例 #1

3 2 1
7 7 7
8 8 8
1 2 3
1 3 2

输出样例 #1

96

输入样例 #2

2 1 0
1 1
1 1
1 -1
1 2

输出样例 #2

0

说明

In the first sample you should first apply the operation of the first type, then the operation of the second type.