配点 : $400$ 点

問題

ある日、ドワンゴ社員のニワンゴくんは、長さ $N$ の整数列 $(a_1, ..., a_N)$ を見つけました。ニワンゴくんは、数列 $a$ の性質に興味を持っています。

数列 $a$ の空でない連続する部分列 $a_l, ..., a_r$ $(1 \leq l \leq r \leq N)$ の 美しさ は、 $a_l + ... + a_r$ と定義されます。ニワンゴくんは、ありうる $N(N+1)/2$ 個の空でない連続する部分列のうち、 $K$ 個を選んで取ってきて、それらの美しさのビット毎の論理積 (AND) を計算したとき、その最大値がどうなるかを知りたがっています (取ってくる部分列の間で重複する要素があっても構いません)。

彼の代わりに最大値を求めてください。

制約

• $2 \leq N \leq 1000$
• $1 \leq a_i \leq 10^9$
• $1 \leq K \leq N(N+1)/2$
• 入力として与えられる数値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$a_1$ $a_2$ $...$ $a_N$

出力

答えを出力せよ。

4 2
2 5 2 5

12

異なる空でない連続する部分列は $10$ 個存在します。全列挙すると、

• 1 番目から始まるもの: $\{2\}, \{2, 5\}, \{2, 5, 2\}, \{2, 5, 2, 5\}$
• 2 番目から始まるもの: $\{5\}, \{5, 2\}, \{5, 2, 5\}$
• 3 番目から始まるもの: $\{2\}, \{2, 5\}$
• 4 番目から始まるもの: $\{5\}$

です (数列の要素が同じでも、異なる添字から始まる列は異なるものとみなすことに注意してください)。

このうち異なる $2$ 個の部分列の美しさのビット毎の論理積 (AND) として得られる値の最大値は $12$ です。 これは $\{5, 2, 5\}$ (美しさ $12$) と $\{2, 5, 2, 5\}$ (美しさ $14$) を選んだ時に達成できます。

8 4
9 1 8 2 7 5 6 4

32