You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

给定一个长度为 $n$ 的整数序列 $a = (a_1, a_2, \dots, a_n)$。你需要将这个序列划分为 $m$ 个非空且连续的子段。对于每一个子段，定义其价值为该子段内所有元素进行 按位与运算的结果。请你规划一种划分方案，使得这 $m$ 个子段的价值之和最大，并输出这个最大值。

形式化定义：你需要找到 $m-1$ 个分割点 $k_1, k_2, \dots, k_{m-1}$（满足 $1 \le k_1 < k_2 < \dots < k_{m-1} < n$），将序列分为 $m$ 段：$[1, k_1], [k_1+1, k_2], \dots, [k_{m-1}+1, n]$。设 $val(l, r) = a_l \ \& \ a_{l+1} \ \& \ \dots \ \& \ a_r$，你需要最大化：

其中 $[L_i, R_i]$ 是第 $i$ 个子段的下标区间。

Input Format

第一行包含两个整数 $n, m$，分别表示序列的长度和需要切分的段数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \le a_i \le 10^9)$，表示信号序列。

Output Format

输出一个整数，表示能获得的最大价值和。

Sample

Input1:

3 2
7 3 1

Output1:

8

Input2:

4 2
10 7 0 15

Output2:

15

Hint

$1 \le n \le 1e5,1 \le m \le 50$, $1 \le a_i \le 1e9$.