Nx3 크기의 격자판이 있어서 각 격자마다 정수가 써져있다. 당신은 이 격자판에 아래 방법과 같이 K개의 1x2크기의 도미노를 올리려고 한다.

- 각 도미노는 정확히 두 개의 격자판을 덮어야 한다.

- 한 격자에 두 개 이상의 도미노를 덮거나 도미노가 격자판 밖을 벗어나면 안 된다.

- 도미노는 돌릴 수 있다.

- K개의 도미노를 모두 사용해야 한다.

- 도미노에 의해 덮힌 격자들에 써져있는 수들의 합은 최대가 되어야 한다.

격자판이 주어질 때, 당신이 얻을 수 있는 값을 구하는 프로그램을 출력하여라.

도미노 (DOMINE) timer 1초 memory 64MB

도미노 (DOMINE) 1초 64MB