남작의 영토

왕은 원정에서 승리한 뒤, 가장 뛰어난 두 지휘관에게 작위와 새로 정복한 영토의 일부를 하사하기로 했다. 새로 임명된 두 남작은 각자 새 영토에 성을 하나씩 짓고 주변 땅에서 세금을 걷을 수 있다.

영토는 격자 지도로 그려져 있으며, 각 칸은 기병이 하루 동안 이동할 수 있는 거리에 해당한다. 각 남작은 성을 지을 칸을 하나 고른다. 당신은 선임 지휘관이므로 먼저 고른다.

성은 선택한 칸의 중심에 있다고 본다. 두 성은 중심 사이의 거리가 3일치 이동 거리를 초과하는(즉 3보다 더 먼) 위치에 지어야 한다.

각 남작은 자기 성의 중심으로부터 거리가 6일치 이동 이하이면서 상대 남작의 성보다 자기 성에 더 가까운 모든 칸에서 세금을 걷는다. 두 성으로부터 거리가 같은 칸은 어느 쪽에도 세금을 주지 않는다.

당신과 동료 지휘관 사이의 긴장은 원정 내내 높아졌고, 언젠가 영토 전체를 두고 싸우게 될 것이다. 그때까지 세금 확보가 병력 증강의 핵심이다. 당신은 상대보다 더 많은 세금을 걷어야 하며, 그 격차를 최대한 벌려야 한다.

당신의 참모는 옛 왕의 기록을 연구하여 각 칸에서 기대되는 연간 세수(금화)를 추정했다. 당신의 우위를 (당신이 걷는 세금) − (상대가 걷는 세금)으로 정의한다. 당신이 먼저 성 위치 $P$를 정하면, 상대는 규칙(두 성 중심 사이 거리가 3을 초과, 0이 아닌 칸)을 지키면서 당신의 우위를 최소화하도록 자기 성을 놓는다. 당신은 이 최악의 경우에서의 우위를 최대로 만드는 위치 $P$를 고른다.

모든 거리는 유클리드 거리이다. 정수 좌표 $(x_1,y_1)$, $(x_2,y_2)$에 있는 두 칸 중심 사이의 거리는 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$이다.

첫 줄에 지도의 너비 $w$와 높이 $h$가 공백으로 구분되어 주어진다 ($1 \le w, h \le 50$).

이어서 $w \times h$개의 정수가 여러 줄에 걸쳐 주어진다. 각 정수는 한 칸의 기대 연간 세수(금화)이며, 다음 순서로 나열된다:

$$(0,0),\ (1,0),\ \dots,\ (w-1,0),\ (0,1),\ (1,1),\ \dots,\ (w-1,h-1)$$

각 값은 $0$ 이상 $40$ 이하이다. 값이 $0$인 칸은 물이거나 사람이 살 수 없는 땅이므로 성을 지을 수 없다.

입력으로 주어지는 모든 지도는, 첫 번째 성을 어디에 놓더라도 두 성을 모두 0이 아닌 칸에 놓을 수 있을 만큼 충분히 크다(상대를 지도 밖으로 완전히 몰아낼 수는 없다).

정수 하나를 출력한다: 당신이 성 위치를 먼저 정하고, 그 뒤 상대가 위 규칙을 지키며 당신의 우위를 최소화하도록 성을 놓을 때, 당신이 보장할 수 있는 우위(= 당신이 걷는 연간 세금 − 상대가 걷는 연간 세금)의 최댓값을 출력한다. 우위는 음수일 수도 있다.