비숍 낙서
시간 제한1초메모리 제한128 MB
2N x 2N 체스판에서 두 비숍을 K번 이동시켜 그동안 어느 비숍의 시야에도 없던 칸들의 합이 최대가 되도록 하는 문제입니다.
문제
선영이는 문제를 풀 때 종이에 낙서를 하곤 한다. 오늘은 2N x 2N 크기의 체스판을 그리고 다음 게임을 한다.
먼저 각 칸에 정수를 하나씩 적는다. 처음에는 첫 번째 행의 가운데 두 칸, 즉 N열과 N+1열에 비숍을 하나씩 둔다. 비숍의 시야는 현재 위치에서 대각선으로 이동할 수 있는 모든 칸이며, 비숍이 서 있는 칸은 시야에 포함하지 않는다.
N = 3일 때 두 비숍의 위치와 시야는 다음과 같다. L은 비숍, X는 시야에 들어오는 칸, O는 그렇지 않은 칸이다.
OOLLOO
OXXXXO
XXOOXX
XOOOOX
OOOOOO
OOOOOO
선영이는 K번의 턴을 수행한다. 점수는 다음 규칙으로 계산된다.
- 어떤 비숍도 움직이기 전, 두 비숍의 시야에 들어오는 모든 칸의 숫자 합이 초기 점수이다.
- 각 턴마다 비숍 하나를 골라, 그 비숍의 현재 시야에 들어오는 칸 중 하나로 이동시킨다.
- 이동 뒤 새 위치에서 보이게 된 칸 중, 게임 시작 이후 한 번도 어떤 비숍의 시야에 들어온 적이 없던 칸들의 숫자 합을 점수에 더한다.
K번의 턴을 모두 수행한 뒤 얻을 수 있는 최대 점수를 구하라.
입력
첫째 줄에 두 정수 N과 K가 주어진다. (1 <= N <= 10, 0 <= K <= 100)
다음 2N개 줄에는 체스판의 각 행에 적힌 2N개의 정수가 주어진다. 각 정수는 -1,000,000 이상 1,000,000 이하이다.
출력
K번의 턴을 모두 수행했을 때 얻을 수 있는 최대 점수를 첫째 줄에 출력한다.