시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 33 10 10 37.037%

문제

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

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

입력

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

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

출력

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

예제 입력 1

3 4
9 1 15 16
3 4 10 6
2 5 7 11

예제 출력 1

42

출처

  • 빠진 조건을 찾은 사람: adh0463
  • 문제의 오타를 찾은 사람: jh05013
  • 잘못된 조건을 찾은 사람: koosaga