[ARC146B] Plus and AND
Score : points
Problem Statement
You are given a sequence of non-negative integers: . You may perform the following operation at most times (possibly zero):
- choose an integer such that and add to .
Then, you will choose of the elements of .
Find the maximum possible value of the bitwise of the elements you choose.
What is bitwise ${\rm AND}$?
The bitwise ${\rm AND}$ of non-negative integers $A$ and $B$, $A\ \mathrm{AND}\ B$, is defined as follows:
- When $A\ {\rm AND}\ B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if both of the digits in that place of $A$ and $B$ are $1$, and $0$ otherwise.
Generally, the bitwise {\rm AND} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
4 8 2
1 2 4 8
10
If you do the following, the bitwise of the elements you choose will be .
- Perform the operation on six times. Now, .
- Perform the operation on twice. Now, .
- Choose and , whose bitwise is .
There is no way to choose two elements whose bitwise is greater than , so the answer is .
5 345 3
111 192 421 390 229
461