| Codeforces Round 122 (Div. 1) |
|---|
| Закончено |
У Джона Доу есть четыре массива 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
В первом примере нужно применить сначала операцию первого типа, а затем операцию второго типа.
