题目描述

你有一个长度为 $n$ 的序列 $a$，现在你可以进行至多 $m$ 次操作。每次操作你可以选择 $1 \le i \le n$，将 $a_i$ 变为 $2\times a_i$。求最终序列 $a$ 的按位或的最小值，即 $\operatorname{or}_{i=1}^na_i$ 的最小值。

$\operatorname{or}$ 为按位或运算。

输入格式

第一行输入一个整数 $n$，表示序列长度。

第二行输入 $n$ 个整数，表示序列 $a$。

第三行输入一个整数 $m$，表示至多进行操作次数。

输出格式

第一行输出 $1$ 个整数，表示答案。

3
5 1 4
1

5

2
1 2
1

2

提示

【样例解释 #1】

可以不进行操作。

【样例解释 #2】

选择 $i = 1$，$a_1$ 变为 $2 \times 1 = 2$，序列 $a$ 的按位或为 $2$。

【数据范围】

本题采用捆绑测试。

• 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\times10 ^ 3$。
• Subtask #4（$35\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10 ^ 6$ , $1 \le m \le 10 ^ 6$ , $0 \le a_i \le 10 ^ 9$。