The province of Bali has many sculptures located on its roads. Let's focus on one of its main roads.
There are
Here is the rule in partitioning the sculptures:
- The sculptures must be partitioned into exactly
groups, where . Each group must consist of at least one sculpture. Each sculpture must belong to exactly one group. The sculptures in each group must be consecutive sculptures on the road. - For each group, compute the sum of the ages of the sculptures in that group.
- Finally, compute the bitwise OR of the above sums. Let's call this the final beauty value of the partition.
What is the minimum final beauty value that the government can achieve?
Note: the bitwise OR of two non-negative integers
- Convert
and into binary. - Let
= number of bits of , and = number of bits of . Let . - Represent
in binary as and in binary as , where and are the th bits of and , respectively. The ( )st bits are the most significant bits, while the th bits are the least significant bits. , in binary, is defined as , where
Input Specification
The first line contains three space-separated integers
Output Specification
A single line containing the minimum final beauty value.
Sample Input
6 1 3
8 1 2 1 5 4
Sample Output
11
Explanation of Sample Output
Partition the sculptures into 2 groups:
Comments
Can we partition the sculptures into only one group?
If![A = 1](https://static.dmoj.ca/static/blank.b44917055649.gif)
, sure. But won't that always give you the maximum beauty value?