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
注意
在第一个示例中,您应该首先应用第一种类型的操作,然后应用第二种类型的操作。