← 返回题目列表

Codeforces · 193/B

B. 异或

中文机器翻译题面 查看原题

John Doe 有四个数组:a、b、k 和 p。每个数组由 n 个整数组成。所有数组的元素都从 1 开始索引。数组 p 是整数 1 到 n 的排列。

约翰为他的朋友和他自己发明了一种游戏。最初,给玩家一个数组 a。玩家必须对 a 连续执行 u 个操作。您可以执行以下操作:

- 操作 1:对于每个 $$i \in \{1, 2, \ldots, n\}$$ 将 ai 更改为 $$a_{i} \oplus b_{i}$$。表达式 $$x \oplus y$$ 表示对数字 x 和 y 应用按位异或运算。给定的操作存在于所有现代编程语言中,例如,在 C++ 和 Java 语言中,它被标记为“^”,在 Pascal 中被标记为“xor”。
- 操作 2:对于每个 $$i \in \{1, 2, \ldots, n\}$$ 将 ai 更改为 api + r。执行此操作时,所有更改都会同时进行。

应用所有 u 操作后,玩家获得的点数由公式 $$s = \sum_{i=1}^{i\leq n} a_i k_i$$ 确定。

John 想知道玩家在游戏中最多可以赢得多少分。帮助他。

输入

第一行包含空格分隔的整数 n、u 和 r (1 ≤ n, u ≤ 30, 0 ≤ r ≤ 100) — 每个数组中的元素数量、操作数量以及描述其中一个操作的数量。

接下来四行中的每一行都包含 n 个空格分隔的整数 — 数组 a、b、k、p。第一行有数组 a,第二行有数组 b,第三行有数组 k,第四行有数组 p。

保证数组a和b的元素为正且不超过104(1≤ai,bi≤104),数组k的元素绝对值不超过104(|k|≤104),p是从1到n的数字的排列。

输出

在单行上打印数字 s — 玩家在约翰​​的游戏中可以赢得的最大分数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #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

注意

在第一个示例中,您应该首先应用第一种类型的操作,然后应用第二种类型的操作。