비숍 낙서

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

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

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

OOLLOO
OXXXXO
XXOOXX
XOOOOX
OOOOOO
OOOOOO

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

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

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

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

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

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