P13565 "CZOI-R5" Bitwise OR

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](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96).

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 one integer on the first line, denoting the answer.

**[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