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

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

문을 열려면 길이가 $N$인 마법 열쇠를 길이가 정확히 $M$인 마법 열쇠로 만들어야 한다. 이때 마법 열쇠의 힘을 최대한 크게 만들어야 한다.

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

길이가 $\ell$인 마법 열쇠에는 다음 4가지 마법 중 하나를 적용하여 길이를 줄일 수 있다.

1. $a_{1}$과 $a_{2}$를 제거하고 앞에 $a_{1}\oplus a_{2}$를 추가하여 길이가 $\ell-1$인 마법 열쇠를 만든다. 수열은 $(a_{1}, a_{2}, a_{3}, \cdots, a_{\ell}) \Rightarrow (a_{1}\oplus a_{2}, a_{3}, \cdots, a_{\ell})$로 바뀐다.
2. $a_{\ell-1}$과 $a_{\ell}$을 제거하고 뒤에 $a_{\ell-1}\oplus a_{\ell}$을 추가하여 길이가 $\ell-1$인 마법 열쇠를 만든다. 수열은 $(a_{1}, \cdots, a_{\ell-2}, a_{\ell-1}, a_{\ell}) \Rightarrow (a_{1}, \cdots, a_{\ell-2}, a_{\ell-1}\oplus a_{\ell})$로 바뀐다.
3. $a_{1}, a_{2}, a_{3}, a_{4}$를 제거하고 앞에 $a_{2}\oplus a_{3}, a_{1}\oplus a_{4}$를 추가하여 길이가 $\ell-2$인 마법 열쇠를 만든다. 수열은 $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, \cdots, a_{\ell}) \Rightarrow (a_{2}\oplus a_{3}, a_{1}\oplus a_{4}, a_{5}, \cdots, a_{\ell})$로 바뀐다.
4. $a_{\ell-3}, a_{\ell-2}, a_{\ell-1}, a_{\ell}$을 제거하고 뒤에 $a_{\ell-3}\oplus a_{\ell}, a_{\ell-2}\oplus a_{\ell-1}$을 추가하여 길이가 $\ell-2$인 마법 열쇠를 만든다. 수열은 $(a_{1}, \cdots, a_{\ell-4}, a_{\ell-3}, a_{\ell-2}, a_{\ell-1}, a_{\ell}) \Rightarrow (a_{1}, \cdots, a_{\ell-4}, a_{\ell-3}\oplus a_{\ell}, a_{\ell-2}\oplus a_{\ell-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$인 마법 열쇠를 만들었을 때 가능한 마법 열쇠의 힘 중 최댓값을 출력한다.

$\oplus$는 비트 단위로 계산하는 비트 XOR 연산이다.

Bitwise XOR

• 두 수의 같은 자리 비트를 비교한다.
  • 두 비트가 서로 다르면 결과는 $1$이고, 같으면 $0$이다.
• 예시:

$\begin{aligned} 0110_{2} &= 6 \\ \oplus \ 1100_{2} &= 12 \\ 1010_{2} &= 10 \end{aligned}$