미르코는 2×N by 2×N 체스판을 그리고 아래의 게임을 하기로 했다.

각각의 사각형에서, 그는 그 사각형의 값을 의미하는 정수를 써 넣었다. 첫 번째 행의 중간에서 (세로줄 N과 N+1), 그는 두 개의 비숍을 두었다.

그리고 미르코는 두 비숍의 시야 범위를 계산했다: 이는 한 비숍의 대각선에 있는 사각형들이다. 하지만 다른 하나의 비숍이 있는 사각형은 포함되지 않는다.

예를 들어, 만약 N이 3이면, 비숍들의 시작 위치(L로 표시)에서 두 비숍의 시야 내에 있는 사각형들(X로 표시)는 다음과 같다:

OOLLOO  
OXXXXO  
XXOOXX  
XOOOOX  
OOOOOO  
OOOOOO  

1. 어떤 움직임을 시작하기 전에, 미르코는 두 비숍의 시야에 있는 사각형들의 값들을 모두 더해서 계산해 보았다. 이것이 미르코의 초기 점수이다.
2. 각각의 턴에서, 미르코는 비숍 하나를 골라 시야 내에 있는 한 사각형으로 이동시켰다.
3. 새 위치에서, 비숍은 이제 새로운 사각형들을 볼 수 있게 되었다. 이 사각형들의 합계에서, 게임 시작할 때 비숍으로부터 가려서 보이지 않은 사각형들이 이제 미르코의 점수에 추가되었다. 미르코가 K턴을 시도했을때 얻을 수 있는 최대 점수를 계산하는 프로그램을 만들어라.

입력

• 입력의 첫 번째 행은 체스판의 크기와 턴 수를 의미하는 두 개의 정수 N i K (1 ≤ N ≤ 10, 0 ≤ K ≤ 100)를 포함한다.
• 다음의 2XN 행은 상응하는 열(열당 2XN의 값을 가짐)에 있는 사각형들의 값을 포함한다.

출력

입출력 예

입력

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

출력

4

입력

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

출력

1

출처:coci
번역:jwvg0425