14258번 - XOR 그룹

문제

N*M 격자에 서로 다른 수가 하나씩 들어가 있다. XOR 그룹이라는 것을 정의를 하여 합을 최대로 하려한다. XOR 그룹이란 위, 아래, 오른쪽, 왼쪽으로 인접한 칸에 수가 있다면, 그 칸과 연결되어 그 수를 모두 XOR한 값을 가지는 그룹이 된다. 만약, 중간에 수가 빠져있으면, 연결이 되지 않으므로, 한 격자판에 여러 XOR 그룹이 있을 수 있다.

이제 격자판에서 작은 수부터 제거해 나갈 것이다. 하나를 지울 때 마다 XOR 그룹이 변하는데, XOR그룹의 값의 합의 최대가 될 때, 그 값을 구하여라.

입력

첫째 줄에 n, m이 주어진다.(1 ≤ n, m ≤ 1,000)

다음 n줄에는 격자의 i번째 줄의 수 m개가 주어진다. 수는 1,000,000보다 크지 않은 음이 아닌 정수이다.

출력

XOR 그룹의 값의 합이 최대가 되는 값을 구하여라

제한

힌트