30473번 - 호반우가 학교에 지각한 이유 6

문제

마왕에게 거의 다다른 호반우지만 마왕의 옥좌로 들어가는 문이 잠겨 못 들어가고 있다.

문을 열기 위해서는 길이가 $N$인 마법 열쇠를 길이가 정확히 $M$인 마법 열쇠로 만들어야 하는데 마법 열쇠의 힘을 최대한 크게 만들어야 한다.

길이가 $N$인 마법 열쇠는 $N$개의 음이 아닌 정수로 이루어진 수열 $a_{1},,円,円a_{2},,円,円a_{3},,円\cdots,,円a_{N}$을 가지며 길이가 $N$인 마법 열쇠의 힘은 수열을 구성하는 $N$개의 수의 합으로 정의한다.

현재 마법 열쇠의 길이가 $l$일 때 마법 열쇠에 다음 4ドル$가지 마법 중 하나를 적용하여 마법 열쇠의 길이를 줄일 수 있다.

1. 마법 열쇠에서 $a_{1},,円a_{2}$를 제거하고 앞에 $a_{1}⊕a_{2}$를 추가하여 길이가 $l-1$인 새로운 마법 열쇠를 만든다.
2. 마법 열쇠에서 $a_{l-1},,円a_{l}$을 제거하고 뒤에 $a_{l-1}⊕a_{l}$을 추가하여 길이가 $l-1$인 새로운 마법 열쇠를 만든다.
3. 마법 열쇠에서 $a_{1},,円a_{2},,円a_{3},,円a_{4}$를 제거하고 앞에 $a_{2}⊕a_{3},,円a_{1}⊕a_{4}$를 추가하여 길이가 $l-2$인 새로운 마법 열쇠를 만든다.
4. 마법 열쇠에서 $a_{l-3},,円a_{l-2},,円a_{l-1},,円a_{l}$을 제거하고 뒤에 $a_{l-3}⊕a_{l},,円a_{l-2}⊕a_{l-1}$을 추가하여 길이가 $l-2$인 새로운 마법 열쇠를 만든다.

각 연산마다 변화를 수열로 나타내면 다음과 같다.

1. $({\color{Red}a_{{\color{Red}1}}},,円,円{\color{Red}a_{{\color{Red}2}}},,円,円a_{3},,円,円a_{4},,円\cdots,,円a_{l}) \Rightarrow ({\color{Red}a_{{\color{Red}1}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}2}}},,円,円a_{3},,円,円a_{4},,円\cdots,,円a_{l})$
2. $(a_{1},,円\cdots,,円a_{l-3},,円,円a_{l-2},,円,円{\color{Red}a_{{\color{Red}l{\color{Red}-}{\color{Red}1}}}},,円,円{\color{Red}a_{{\color{Red}l}}}) \Rightarrow (a_{1},,円\cdots,,円a_{l-3},,円,円a_{l-2},,円,円{\color{Red}a_{{\color{Red}l}{\color{Red}-}{\color{Red}1}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}l}}})$
3. $({\color{Red}a_{{\color{Red}1}}},,円,円{\color{Blue}a_{{\color{Blue}2}}},,円,円{\color{Blue}a_{{\color{Blue}3}}},,円,円{\color{Red}a_{{\color{Red}4}}},,円,円a_{5},,円,円a_{6},,円\cdots,,円a_{l}) \Rightarrow ({\color{Blue}a_{{\color{Blue}2}}}{\color{Blue}⊕}{\color{Blue}a_{{\color{Blue}3}}},,円,円{\color{Red}a_{{\color{Red}1}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}4}}},,円,円a_{5},,円,円a_{6},,円\cdots,,円a_{l})$
4. $(a_{1},,円\cdots,,円a_{l-5},,円,円a_{l-4},,円,円{\color{Red}a_{{\color{Red}l}{\color{Red}-}{\color{Red}3}}},,円,円{\color{Blue}a_{{\color{Blue}l}{\color{Blue}-}{\color{Blue}2}}},,円,円{\color{Blue}a_{{\color{Blue}l}{\color{Blue}-}{\color{Blue}1}}},,円,円{\color{Red}a_{{\color{Red}l}}}) \Rightarrow (a_{1},,円\cdots,,円a_{l-5},,円,円a_{l-4},,円,円{\color{Red}a_{{\color{Red}l}{\color{Red}-}{\color{Red}3}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}l}}},,円,円{\color{Blue}a_{{\color{Blue}l}{\color{Blue}-}{\color{Blue}2}}}{\color{Blue}⊕}{\color{Blue}a_{{\color{Blue}l}{\color{Blue}-}{\color{Blue}1}}})$

호반우가 문을 열어 마왕에게 갈 수 있도록 도와주자!

입력

첫 번째 줄에 마법 열쇠의 길이 $N$과 목표 길이 $M$이 공백을 두고 주어진다. $(4 \le M \le N \le 3,000円)$

두 번째 줄에 $N$개의 수 $a_{1},,円,円a_{2},,円,円a_{3},,円\cdots,,円a_{N}$이 공백을 두고 주어진다. $(0 \le a_{i} \le 10^{9})$

출력

길이가 $M$인 마법 열쇠를 만들었을 때 가능한 마법 열쇠의 힘 중 최댓값을 출력한다.

제한

힌트

⊕는 Bitwise XOR 연산이며 비트 단위로 연산을 시행한다.

• Bitwise XOR
  • 두 수의 비트마다 아래와 같은 연산을 진행한다.
    • 두 비트가 서로 다르면 결과가 1ドル$이고, 그렇지 않으면 0ドル$이다.
  • 예시
    • $\begin{aligned} 0110_{2} &= 6 \\ \text{⊕} \ \ 1100_{2} &= 12 \\ \text{────} \\ 1010_{2} &= 10 \end{aligned}$