Minimum Cost Oil Depot Placement

In the holy land of Sanctuary, Morris Joe is a mighty figure controlling the oil market with his keen economic mind. The map of Sanctuary is represented as an \(n\times m\) grid where each integer coordinate \((x,y)\) (with \(1 \le x \le n,\; 1 \le y \le m\)) denotes a city. Two cities \((A_x, A_y)\) and \((B_x, B_y)\) are adjacent if and only if \((A_x - B_x)^2 + (A_y - B_y)^2 = 1\).

Every city must satisfy one of the following conditions:

1. The city itself has an oil depot.
2. At least one adjacent city has an oil depot.

Each city \((x,y)\) has an associated building cost \(c_{x,y}\) for constructing an oil depot. Morris Joe's objective is to build depots so that every city is covered while minimizing the total cost \[ \sum_{(x,y) \in S} c_{x,y}, \] where \(S\) is the set of cities chosen for depot construction. If multiple configurations yield the same minimum total cost, then the configuration with the fewest number of depots is chosen.

Your task is to compute and output two integers: the minimum total cost and the number of depots used in the optimal configuration.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) representing the number of rows and columns of the grid. Following this, there are \(n\) lines, each containing \(m\) integers. The \(j\)-th integer in the \(i\)-th line represents the cost \(c_{i,j}\) of building an oil depot in city \((i, j)\).

Constraints: You may assume that the grid is small enough (e.g. \(n \times m \leq 20\)) so that a brute-force solution using bitmask enumeration is feasible.

outputFormat

Output two integers separated by a space: the first integer is the minimum total cost to cover all the cities, and the second is the number of oil depots built in the optimal configuration.

sample

1 1
5

5 1