비숍 낙서

선영이는 문제를 풀 때 종이에 낙서를 하곤 한다. 오늘은 2N x 2N 크기의 체스판을 그리고 다음 게임을 한다.

먼저 각 칸에 정수를 하나씩 적는다. 처음에는 첫 번째 행의 가운데 두 칸, 즉 N열과 N+1열에 비숍을 하나씩 둔다. 비숍의 시야는 현재 위치에서 대각선으로 이동할 수 있는 모든 칸이며, 비숍이 서 있는 칸은 시야에 포함하지 않는다.

N = 3일 때 두 비숍의 위치와 시야는 다음과 같다. L은 비숍, X는 시야에 들어오는 칸, O는 그렇지 않은 칸이다.

OOLLOOOXXXXOXXOOXXXOOOOXOOOOOOOOOOOO

선영이는 K번의 턴을 수행한다. 점수는 다음 규칙으로 계산된다.

1. 어떤 비숍도 움직이기 전, 두 비숍의 시야에 들어오는 모든 칸의 숫자 합이 초기 점수이다.
2. 각 턴마다 비숍 하나를 골라, 그 비숍의 현재 시야에 들어오는 칸 중 하나로 이동시킨다.
3. 이동 뒤 새 위치에서 보이게 된 칸 중, 게임 시작 이후 한 번도 어떤 비숍의 시야에 들어온 적이 없던 칸들의 숫자 합을 점수에 더한다.

K번의 턴을 모두 수행한 뒤 얻을 수 있는 최대 점수를 구하라.

첫째 줄에 두 정수 N과 K가 주어진다. (1 <= N <= 10, 0 <= K <= 100)

다음 2N개 줄에는 체스판의 각 행에 적힌 2N개의 정수가 주어진다. 각 정수는 -1,000,000 이상 1,000,000 이하이다.

K번의 턴을 모두 수행했을 때 얻을 수 있는 최대 점수를 첫째 줄에 출력한다.