시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

선영이는 문제를 풀 때 종이에 낙서를 한다. 오늘은 2×N by 2×N 크기의 체스판을 그렸다.

오늘은 아래 설명과 같은 게임을 할 것이다.

먼저 각 칸에 정수를 써 놓는다. 먼저, 첫 번째 행의 중간(N열, N+1열)에 비숍 두 개를 놓는다. 그 다음에 선영이는 비숍의 시야를 표시한다.

비숍의 시야란 비숍이 이동할 수 있는 칸이다.

예를 들어, N이 3일 때, 두 비숍의 시야는 아래 그림과 같다. 비숍은 L로 표시하고, 시야는 X로 표시한다.

OOLLOO
OXXXXO
XXOOXX
XOOOOX
OOOOOO
OOOOOO

선영이가 비숍을 움직일 수 있는 횟수는 제한이 있다. 따라서, 아래와 같은 전략으로 최대 점수를 얻으려고 한다.

1. 비숍을 움직이기 전에, 비숍의 시야에 들어있는 칸에 써 있는 숫자의 합을 계산한다. 이 합이 초기 점수이다.

2. 각 턴을 수행할 때, 선영이는 두 비숍중 하나를 고르고, 그 시야에 있는 칸 중 하나로 이동한다.

3. 비숍을 새 위치로 이동시키면, 이전에는 볼 수 없었던 새로운 칸을 볼 수 있다. 자 이제 게임을 시작하고 단 한 번도 비숍의 시야에 들어온 적이 없지만, 이번 이동으로 새로이 비숍의 시야에 들어온 칸에 써 있는 숫자의 합을 구한다. 이 합을 점수에 추가한다.

선영이가 턴을 K번 수행했을 때 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력

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

다음 2×N개 줄에는 해당하는 행에 써 있는 숫자 2×N개가 주어진다. 각 숫자는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 선영이가 얻을 수 있는 최대 점수를 출력한다.

예제 입력

2 0
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0

예제 출력

4

힌트