시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 49 20 17 40.476%

문제

(주) 넝심에서는 양파링의 아성에 도전할 만한 아이디어 과자인 양파깡을 만들어냈다. 양파깡은 기존의 양파링과는 달리 직사각형의 모양을 갖는 과자이다. 그런데 (주) 넝심의 과자 기술은 그리 발달된 것이 아니라서 양파깡의 모양을 바로 만들지 못한다. 그래서 궁여지책으로 생각한 것이 넙적한 과자판을 만들어서 양파깡의 모양으로 잘라내는 방법이다.

양파깡으로 잘라내기 전에 먼저 과자판에 소스(양념가루)를 골고루 뿌려야 하는데, 공정상의 실수로 소스가 엉망으로 뿌려지게 되었다. 이 소스는 많으면 많을수록 과자의 맛이 좋다고 한다.

과자판은 NxN크기의 정사각 배열로서 표현될 수 있으며, 각각의 요소는 그 부분에 뿌려진 소스의 양을 나타낸다. 양수는 원래 기준치 소스양보다  많이 뿌려졌음을, 음수는 그 반대를 나타낸다. 다음은 10x10크기의 과자판의 예이다.

양파깡은 다음과 같이 가운데가 빈 직사각형 모양으로 생겼다. (꼭 가운데에 빈 공간이 있어야 한다. 즉, 양파깡은 최소 3x3이상의 크기를 가져야 한다.) 양파깡은 도중에 끊어지지 않은 모양이어야 한다.

양파깡의 맛은 잘라낸 부분의 소스의 양들의 합으로 정의된다. 위의 양파깡의 맛은 3 + 5 + (-1) + (-2) + 4 + (-5) + 3 + 7 + 1 + 0 + (-6) + 4 + 3 + 2 + 4 + (-3) + 1 + (-2) = 18 이다.

당신은 (주) 넝심의 수석 프로그래머로써 상사의 명령에 따라 과자판으로부터 양파깡을 잘라내는 프로그램을 만들어야 한다. 상사가 원하는 프로그램은 다음과 같다.

(1) 현재 만들어질 수 있는 양파깡 중에서 가장 맛있도록 양파깡을 잘라내야 한다.

(2) 이런 방법으로 M번 반복하여 M개의 양파깡을 잘라낸다.

(3) 만들어진 모든 양파깡 들은 도중에 끊어지지 않고 가운데가 빈 모양이어야 한다.

양파깡이 도중에 끊어지지 않아야 한다는 말은 과자판에서 양파깡들이 서로 겹치지 않아야 된다는 말과 같은 뜻이다.

예로 위의 과자판에서 4개의 양파깡을 만들어 내는 문제를 생각해 보자. 첫번째로 만들 수 있는 가장 맛 좋은 양파깡은 (3, 1)-(10, 9) 위치에서 잘라내면 만들 수 있다. 이 때의 양파깡의 맛은 48이다.

과자판에서 양파깡을 잘라내면 다음과 같은 모양이 된다.

이 과자판에서 가장 맛 좋은 양파깡을 찾아보면 (7, 5)-(9, 7) 부분을 잘라내면 된다. 이 양파깡의 맛은 6이다.

이런 식으로 4개의 양파깡을 만들어 내면 된다.

NxN(3≤N≤30)개의 과자판이 주어질 때, 상사의 요구를 만족시는 프로그램을 작성하시오.

입력

맨 첫줄에는 과자판의 크기 N과 잘라낼 양파깡의 개수 M(1≤M≤30)이 빈 칸을 사이에 두고 주어진다. 다음 줄부터는 과자판이 NxN의 형태로 빈칸을 사이에 두고 주어진다. 각 소스의 수는 -100이상 100이하의 정수이다.

출력

첫번째 줄부터 잘라낸 순서대로 양파깡의 정보를 M줄 만큼 출력한다. 만약 상사의 요구를 만족하는 양파깡을 M개 잘라내는 것이 불가능하다면 맨 첫줄에 0만을 출력한다.

양파깡의 정보는 처음에 양파깡의 맛을 출력하고, 그 뒤에 양파깡의 위치를 출력한다. 양파깡의 위치는 왼쪽 위의 좌표를 나타내는 두 숫자(행, 열의 순서)와 오른쪽 아래의 좌표를 나타내는 두 숫자를 차례대로 쓴다.

항상 답이 유일한 경우만 입력으로 주어진다.

예제 입력

10 4
   1   -5    0    8   -1   -8   -3    5    4   -5
  -4   10   -1   -6   -3    8   -4    4   -8   -8
  -2   -4   -7   -6    7    2   -5   10   -9   -3
   9    9   -7   -6   -6   -3   -8   -6    8    6
  10    4   -2    2   -3   -9   -5    7   -4   -6
   0    7    0   -7   -7   -7  -10   -5   -2    7
   3  -10    0   -5    6   -2    3   -7    8   -3
   9   -6   -8   -1    0   -1   -4   -3   -9    6
  10   -4   -1   -7   -2   10   -5   -3    8   -7
   0    5   -4    8   -3    0   -7   10    3    3 

예제 출력

48 3 1 10 9
6 7 5 9 7
2 4 2 6 4
-34 7 2 9 4

힌트