/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は、N 個のランプが一列に並んだ装置を持っています。各ランプは点灯（1）または消灯（0）のいずれかの状態です。
ランプを左から順に b_1, b_2, \ldots, b_N と表すと、この装置の状態は整数
X = \sum_{i=1}^{N} b_i \cdot 2^{i-1}
で表されます。すなわち、左から i 番目のランプ b_i が X の 2 進表現における下から i ビット目に対応します（左端が最下位ビットです）。
高橋君の装置に対して、以下の操作が繰り返し行われます。操作は最大 K 回行われますが、途中で停止することがあります。
1回の操作： 現在の列の左端のランプを確認する。
- それが点灯（1）であれば、何もせずに全操作を終了する。
- それが消灯（0）であれば、そのランプを列から取り除き、右端に点灯（1）状態のランプを 1 つ追加する（列の長さは N のまま保たれる）。まだ操作回数が K 回に達していなければ、再び操作を行う。
すなわち、「左端が消灯であるかぎり、それを取り除いて右端に点灯ランプを追加する」という操作を、最大 K 回まで行います。左端が点灯であることを確認した時点、または操作を K 回行った時点で処理は終了します。
この処理の後、青木君が M 個のランプ列を持ってきます。各ランプ列も長さ N であり、j 番目のランプ列の状態は整数 Y_j で、高橋君の装置と同様のビット対応で表されます。
高橋君は、処理後の自分のランプ列と青木君の M 個のランプ列、合計 M + 1 個のランプ列すべてに対して、共通の分割位置 p（1 \le p \le N - 1）を 1 つ選びます。各ランプ列は、左側 p 個と右側 N - p 個に分けられます。
各ランプ列について、左側部分のランプを左から順に c_1, c_2, \ldots, c_p としたとき、その整数値を
\sum_{i=1}^{p} c_i \cdot 2^{i-1}
で定めます。M+1 個のランプ列の左側部分の整数値の総和を A とします。
同様に、各ランプ列について、右側部分のランプを左から順に d_1, d_2, \ldots, d_{N-p} としたとき、その整数値を
\sum_{i=1}^{N-p} d_i \cdot 2^{i-1}
で定めます（右側部分内で改めて 2^0 から数え直すことに注意してください）。M+1 個のランプ列の右側部分の整数値の総和を B とします。
高橋君は A + B を最大化するように分割位置 p を選びます。A + B の最大値を求めてください。
制約
- 2 \leq N \leq 46
- 0 \leq K \leq 10^9
- 0 \leq M \leq 2 \times 10^5
- 0 \leq X < 2^N
- 0 \leq Y_j < 2^N（1 \leq j \leq M）
- 入力はすべて整数である
- この制約のもとで、答えは signed 64-bit integer に収まる
入力
N K M X Y_1 Y_2 \ldots Y_M
1 行目には、ランプ列の長さ N、操作回数の上限 K、追加ランプ列の個数 M、高橋君の装置の初期状態 X が、スペース区切りで与えられる。
M \geq 1 のとき、2 行目には、M 個の追加ランプ列の状態を表す整数 Y_1, Y_2, \ldots, Y_M が、スペース区切りで与えられる。
M = 0 のとき、2 行目は存在しない。
出力
A + B の最大値を 1 行で出力せよ。
入力例 1
5 2 2 4 3 16
出力例 1
23
入力例 2
4 0 1 9 6
出力例 2
8
入力例 3
12 7 6 1384 0 4095 2730 1365 2048 1234
出力例 3
7616
入力例 4
46 1000000000 10 35184372088832 0 1 70368744177663 70368744177662 35184372088831 35184372088832 1234567890123 45678901234567 60000000000000 42
出力例 4
194194222917695
入力例 5
2 1000000000 0 0
出力例 5
2
Score : 333 pts
Problem Statement
Takahashi has a device with N lamps arranged in a row. Each lamp is either on (1) or off (0).
Denoting the lamps from left to right as b_1, b_2, \ldots, b_N, the state of the device is represented by the integer
X = \sum_{i=1}^{N} b_i \cdot 2^{i-1}
That is, the i-th lamp from the left, b_i, corresponds to the i-th bit from the bottom in the binary representation of X (the leftmost lamp is the least significant bit).
The following operation is repeatedly performed on Takahashi's device. The operation is performed at most K times, but may stop midway.
One operation: Check the leftmost lamp of the current sequence.
- If it is on (1), do nothing and terminate all operations.
- If it is off (0), remove that lamp from the sequence and append one on (1) lamp to the right end (the length of the sequence remains N). If the number of operations has not yet reached K, perform the operation again.
In other words, "as long as the leftmost lamp is off, remove it and append an on lamp to the right end" is performed up to K times. The process terminates when the leftmost lamp is confirmed to be on, or when K operations have been performed.
After this process, Aoki brings M lamp sequences. Each lamp sequence also has length N, and the state of the j-th lamp sequence is represented by the integer Y_j, using the same bit correspondence as Takahashi's device.
Takahashi chooses a single common split position p (1 \le p \le N - 1) for all M + 1 lamp sequences — his own processed lamp sequence and Aoki's M lamp sequences. Each lamp sequence is divided into the left p lamps and the right N - p lamps.
For each lamp sequence, letting the lamps of the left part from left to right be c_1, c_2, \ldots, c_p, its integer value is defined as
\sum_{i=1}^{p} c_i \cdot 2^{i-1}
Let A be the sum of the integer values of the left parts of all M+1 lamp sequences.
Similarly, for each lamp sequence, letting the lamps of the right part from left to right be d_1, d_2, \ldots, d_{N-p}, its integer value is defined as
\sum_{i=1}^{N-p} d_i \cdot 2^{i-1}
(Note that the powers of 2 restart from 2^0 within the right part.) Let B be the sum of the integer values of the right parts of all M+1 lamp sequences.
Takahashi chooses the split position p to maximize A + B. Find the maximum value of A + B.
Constraints
- 2 \leq N \leq 46
- 0 \leq K \leq 10^9
- 0 \leq M \leq 2 \times 10^5
- 0 \leq X < 2^N
- 0 \leq Y_j < 2^N (1 \leq j \leq M)
- All inputs are integers
- Under these constraints, the answer fits in a signed 64-bit integer
Input
N K M X Y_1 Y_2 \ldots Y_M
The first line contains the length of the lamp sequence N, the maximum number of operations K, the number of additional lamp sequences M, and the initial state of Takahashi's device X, separated by spaces.
When M \geq 1, the second line contains M integers Y_1, Y_2, \ldots, Y_M representing the states of the additional lamp sequences, separated by spaces.
When M = 0, the second line does not exist.
Output
Output the maximum value of A + B in one line.
Sample Input 1
5 2 2 4 3 16
Sample Output 1
23
Sample Input 2
4 0 1 9 6
Sample Output 2
8
Sample Input 3
12 7 6 1384 0 4095 2730 1365 2048 1234
Sample Output 3
7616
Sample Input 4
46 1000000000 10 35184372088832 0 1 70368744177663 70368744177662 35184372088831 35184372088832 1234567890123 45678901234567 60000000000000 42
Sample Output 4
194194222917695
Sample Input 5
2 1000000000 0 0
Sample Output 5
2