행렬 자르기

Shekhu 교수에게 N개의 행과 M개의 열로 이루어진 행렬이 있다. 행에는 위에서 아래로 0부터 N-1까지 번호가 매겨져 있고, 열에는 왼쪽에서 오른쪽으로 0부터 M-1까지 번호가 매겨져 있다. 행렬의 각 칸에는 양의 정수가 들어 있다.

그는 가로 방향과 세로 방향으로 잘라 이 행렬을 N * M개의 부분 행렬(각각의 크기는 1 * 1)로 만들려고 한다. 자르기는 두 행 사이 또는 두 열 사이의 경계에서만 할 수 있다.

Shekhu 교수는 이 일을 위해 자신의 가장 뛰어난 학생 Akki를 초대하고 흥미로운 제안을 한다. Akki가 부분 행렬을 자를 때마다, 자르기 전에 그 부분 행렬의 최솟값과 같은 수의 동전을 받는다. 자를 때마다 부분 행렬의 총개수가 증가한다는 점에 유의한다. 또한 서로 다른 임의의 두 부분 행렬에서 이루어지는 자르기는 서로 독립적이며, 마찬가지로 Akki는 서로 다른 부분 행렬에서 이루어지는 자르기에 대해 독립적으로 동전을 받는다.

이제 Akki가 자를 수 있는 방법은 여러 가지이다. 그가 얻을 수 있는 동전의 총개수를 최대화하도록 도와주자.

제한

1 ≤ T ≤ 100. 메모리 제한: 1GB. 1 ≤ 행렬의 각 값 ≤ $10^{5}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 40초. N = 1. 1 ≤ M ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ N ≤ 40. 1 ≤ M ≤ 40.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 위에서 설명한 두 정수 N과 M이 주어진다.

• 이어지는 N개의 줄에는 각각 M개의 양의 정수가 주어지며, 이들이 행렬을 나타낸다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 Akki가 최적의 순서로 자를 때 받을 수 있는 동전의 최대 개수이다.

예제 케이스 #1에서 Akki가 자를 수 있는 방법은 두 가지이다.

• Akki가 먼저 행렬을 가로 방향으로 자른다고 하자. 그는 행렬의 최솟값인 1을 받는다. 그런 다음 두 부분 행렬($[1, 2]$와 $[3, 4]$)을 세로 방향으로 잘라야 하며, 이에 대해 각각 1개와 3개의 동전을 받는다.

• Akki가 먼저 행렬을 세로 방향으로 자른다고 하자. 그는 행렬의 최솟값인 1을 받는다. 그런 다음 두 부분 행렬(전치 행렬이 $[1, 3]$와 $[2, 4]$인 부분 행렬)을 가로 방향으로 잘라야 하며, 이에 대해 각각 1개와 2개의 동전을 받는다.

첫 번째 전략이 더 좋으며, 정답은 5이다.

예제 케이스 #2에서 Akki가 받을 수 있는 동전은 최대 7개이다. 최적의 방법 중 하나는 먼저 유일한 가로 방향 자르기를 수행하여 동전 1개를 받는 것이다. 그런 다음 위쪽 부분 행렬 $[1, 2, 1]$에서 Akki는 먼저 첫 번째 열 바로 오른쪽을 자르고, 이어서 두 번째 열 바로 오른쪽을 잘라 총 2개의 동전을 받을 수 있다. 마찬가지로 아래쪽 부분 행렬 $[2, 3, 2]$에서 Akki는 먼저 두 번째 열 바로 오른쪽을 자르고, 이어서 첫 번째 열 바로 오른쪽을 잘라 총 4개의 동전을 받을 수 있다.

예제 케이스 #3에서는 수행해야 할 자르기가 하나뿐이다.