题目描述

云小斗得到了一串宝石，这串宝石从左到右共有 $n$ 颗，第 $i$ 颗宝石的能量值为 $v_i$。

现在，云小斗想把这串宝石分成恰好 $k$ 段。每一段都必须是连续的一段宝石，并且不能为空。

对于一段宝石，定义它的权值为这一段中所有宝石能量值的按位或结果。也就是说，如果这一段包含的能量值依次为 $a_1,a_2,\ldots,a_t$，那么这一段的权值为：

$a_1~\operatorname{or}~a_2~\operatorname{or}~\cdots~\operatorname{or}~a_t$

其中 $\operatorname{or}$ 表示按位或运算。

整个宝石串的权值定义为所有段的权值之和。

云小斗想知道，在所有合法的分段方案中，整个宝石串的最大权值是多少？

输入格式

从文件 diamond.in 中读入数据。

第一行两个整数 $n,k$，表示宝石的数量以及需要分成的段数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 颗宝石的能量值 $v_i$。

输出格式

输出到文件 diamond.out 中。

输出一个整数，表示整个宝石串可能得到的最大权值。

输入输出样例

输入样例 1

5 2
7 5 8 2 3

输出样例 1

22

样例 1 说明

一种最优的分段方式为：第一段只包含第 $1$ 颗宝石，第二段包含第 $2\sim 5$ 颗宝石。

第一段为 $[7]$，这一段的权值为 $7$。

第二段为 $[5,8,2,3]$，这一段的权值为：

$5~\operatorname{or}~8~\operatorname{or}~2~\operatorname{or}~3=15$

因此整个宝石串的权值为：

$7+15=22$

可以证明，不存在权值和更大的分段方案，因此答案为 $22$。

样例 2

见下发文件中 $\textbf{\textit{diamond2.in}}$ 与 $\textbf{\textit{diamond2.out}}$。

说明

数据规模与约定

对于 $30\%$ 的数据，满足 $n\le 10$，$k\le 10$。

对于 $60\%$ 的数据，满足 $n\le 100$，$k\le 100$。

对于 $100\%$ 的数据，满足 $k\le n\le 2000$，$1\le v_i\le 5\times 10^5$。