302968: CF578B. "Or" Game

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

"Or" Game

题意翻译

现在有n个数$a_1,a_2,a_3,...,a_n$ 。你最多可以进行k次操作,每次操作你可以将其中一个数乘以$x$ 。找出使得$a_1|a_2|...|a_n$ 最大的方法,”|“代表位或。

题目描述

You are given $ n $ numbers $ a_{1},a_{2},...,a_{n} $ . You can perform at most $ k $ operations. For each operation you can multiply one of the numbers by $ x $ . We want to make ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF578B/4957ea745191dedda7c88dd7a9c0749def3ef4fd.png) as large as possible, where ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF578B/228ea8924d84782194ed9458038dbd5525d21a6e.png) denotes the bitwise OR. Find the maximum possible value of ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF578B/4957ea745191dedda7c88dd7a9c0749def3ef4fd.png) after performing at most $ k $ operations optimally.

输入输出格式

输入格式


The first line contains three integers $ n $ , $ k $ and $ x $ ( $ 1<=n<=200000 $ , $ 1<=k<=10 $ , $ 2<=x<=8 $ ). The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=10^{9} $ ).

输出格式


Output the maximum value of a bitwise OR of sequence elements after performing operations.

输入输出样例

输入样例 #1

3 1 2
1 1 1

输出样例 #1

3

输入样例 #2

4 2 3
1 2 4 8

输出样例 #2

79

说明

For the first sample, any possible choice of doing one operation will result the same three numbers $ 1 $ , $ 1 $ , $ 2 $ so the result is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF578B/aa4bd67912899e33d42fc5cdc56c32c5fb40c4e1.png). For the second sample if we multiply $ 8 $ by $ 3 $ two times we'll get $ 72 $ . In this case the numbers will become $ 1 $ , $ 2 $ , $ 4 $ , $ 72 $ so the OR value will be $ 79 $ and is the largest possible result.

Input

题意翻译

现在有n个数$a_1,a_2,a_3,...,a_n$ 。你最多可以进行k次操作,每次操作你可以将其中一个数乘以$x$ 。找出使得$a_1|a_2|...|a_n$ 最大的方法,”|“代表位或。

加入题单

上一题 下一题 算法标签: