피자 배달

당신이 운영하는 아일랜드식 피자·케밥 가게가 크게 번창하고 있습니다. 거의 매일 저녁 가게가 손님으로 가득 찰 뿐 아니라, 도시 곳곳으로의 배달 주문도 갈수록 늘고 있습니다. 이 수요를 감당하려면 배달 서비스를 가게에서 분리해야 한다는 결론에 이르렀습니다. 오직 피자를 굽고 배달의 거점 역할만 하는 새 대형 주방을 도시 어딘가에 마련하려고 합니다.

배달 서비스의 가장 큰 비용은 피자를 만드는 일 자체가 아니라 배달에 걸리는 시간입니다. 이를 최소화하려면 새 주방의 위치를 신중하게 정해야 합니다. 다행히 지난해의 모든 배달 기록이 담긴 데이터베이스가 있어, 도시의 각 지점에 지난해 몇 건의 배달이 있었는지 알 수 있습니다. 앞으로의 수요 패턴도 지난해와 같으리라는 가정 아래 주방 위치를 정합니다.

이 도시는 전형적인 교외 형태로, 크기가 같은 정사각형 구획이 직교 격자를 이룹니다. 모든 관심 지점(배달지와 주방)은 교차로에 위치한다고 봅니다. 두 교차로 사이의 거리는 맨해튼 거리, 즉 세로로 지나야 하는 구획 수와 가로로 지나야 하는 구획 수의 합입니다. 한 배달지의 비용은 주방으로부터의 맨해튼 거리에 그 지점으로의 배달 건수를 곱한 값입니다. 비용에는 주방에서 배달지로 가는 거리만 포함합니다. 배달을 마치면 항상 주방으로 곧장 돌아오지만, 이 (같은) 거리는 비용에 넣지 않습니다.

첫 줄에 테스트 케이스의 수 $n$ ($1 \le n \le 20$)이 주어집니다.

각 테스트 케이스는 두 정수 $x$와 $y$ ($1 \le x \le 100$, $1 \le y \le 100$)가 적힌 줄로 시작하며, 이는 2차원 도로 격자의 크기를 나타냅니다. 이어서 $y$개의 줄이 주어지고, 각 줄에는 $x$개의 정수 $d$ ($0 \le d \le 1000$)가 있어, 해당 교차로로 지난해 이루어진 배달 건수를 나타냅니다.

각 테스트 케이스마다 주방을 최적의 위치에 두었다고 가정했을 때 가능한 최소 총 배달 비용(지난해 모든 배달 비용의 합)을 출력합니다. 테스트 케이스마다 한 줄에, 비용을 나타내는 정수 하나를 출력한 뒤 공백 하나와 단어 blocks를 이어 붙여 출력합니다.