B. Xor
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Джона Доу есть четыре массива a, b, k и p. Каждый из них состоит из n целых чисел. Элементы всех массивов индексируются начиная c 1. Массив p является перестановкой целых чисел от 1 до n.

Джон придумал игру для себя и своих друзей. Изначально игроку предлагается массив a. Игрок должен последовательно выполнить ровно u операций над a. Разрешается выполнять следующие операции:

  • Операция 1: Для каждого изменить ai на . Выражение обозначает применение операции побитового исключающего или к числам x и y. Данная операция есть во всех современных языках программирования, например, в языке C++ и Java она обозначается «^», в Pascal — «xor».
  • Операция 2: Для каждого изменить ai на api + r. При выполнении этой операции все изменения происходят одновременно.

После применения всех u операций, количество очков, которые получает игрок, определяется по формуле .

Джон хочет узнать какое максимальное количество очков можно набрать в его игре. Помогите ему.

Входные данные

В первой строке записаны разделенные пробелом целые числа 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 по модулю (|ki| ≤ 104) и p является перестановкой чисел от 1 до n.

Выходные данные

Выведите в единственной строке число s — максимальное количество очков, которое можно получить в игре Джона.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3 2 1
7 7 7
8 8 8
1 2 3
1 3 2
Выходные данные
96
Входные данные
2 1 0
1 1
1 1
1 -1
1 2
Выходные данные
0
Примечание

В первом примере нужно применить сначала операцию первого типа, а затем операцию второго типа.