Problem Description

You have a sequence $a$ of length $n$. Now you can perform at most $m$ operations. In each operation, you may choose an index $1 \le i \le n$ and change $a_i$ to $2 \times a_i$. Find the minimum possible value of the bitwise OR of the final sequence $a$, that is, the minimum of $\operatorname{or}_{i=1}^n a_i$.

$\operatorname{or}$ refers to the bitwise OR operation.

Input Format

The first line contains an integer $n$, denoting the length of the sequence.

The second line contains $n$ integers, denoting the sequence $a$.

The third line contains an integer $m$, denoting the maximum number of operations.

Output Format

Output one integer on the first line, denoting the answer.

3
5 1 4
1

5

2
1 2
1

2

Hint

[Sample Explanation #1]

You may choose to perform no operations.

[Sample Explanation #2]

Choose $i = 1$, then $a_1$ becomes $2 \times 1 = 2$, and the bitwise OR of the sequence $a$ is $2$.

[Constraints]

This problem uses bundled testdata.

• Subtask #1 ($15\text{ pts}$): $n \le 8$, $m \le 8$, $a_i \le 10^3$.
• Subtask #2 ($25\text{ pts}$): $n \le 10^3$, $m \le 10^4$, $a_i \le 10^6$.
• Subtask #3 ($25\text{ pts}$): $n \le 10^3$, $a_i \le 2 \times 10^3$.
• Subtask #4 ($35\text{ pts}$): No special constraints.

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le m \le 10^6$, $0 \le a_i \le 10^9$.

Translated by ChatGPT 5