P3888 [GDOI2014] Save Morris

Morris Qiao is a formidable figure in the Sanctuary. With his outstanding economic acumen, he firmly controls the oil market there. The map of the Sanctuary can be seen as an $n \times m$ grid. Each integer coordinate $(x, y)$ represents a city ($1 \le x \le n, 1 \le y \le m$). The definition of adjacency between two cities is: for cities $(A_x, A_y)$ and $(B_x, B_y)$, they are adjacent if $(A_x - B_x)^2 + (A_y - B_y)^2 = 1$. Because the total volume of oil trade in the Sanctuary is large, Morris realizes that he cannot dispatch every oil order from the same depot. To improve efficiency, Morris Qiao decides to build depots in some cities, so that every city $X$ satisfies one of the following: 1. City $X$ has a depot itself. 2. There exists a city $Y$ with a depot, and city $X$ is adjacent to city $Y$. As on Earth, land prices may differ between cities in the Sanctuary, so Morris wants to minimize the total cost of achieving the goal. If multiple plans have the same minimum total cost, to facilitate management, Morris will choose the one with fewer depots.

The first line contains two positive integers $n, m$ (with $n \times m \le 50$ and $m \le n$), representing the size of the grid. Then follows an $n$-by-$m$ matrix $F$, where $F_{i, j}$ denotes the cost to build a depot in city $(i, j)$.

Output two numbers: the number of depots and the minimum total cost.

For $30\%$ of the testdata, $n \times m \le 25$. For $100\%$ of the testdata, $n \times m \le 50$, $0 \le F_{i, j} \le 10^5$. Translated by ChatGPT 5