Minimum Volunteer Assignment in Scenic Grid

In the city of Shaoxing, the post of scenic spots has been divided into an N × M grid. Each block is either a scenic spot (denoted by X) or a road. A road block has an associated non‐negative integer cost which represents the minimum number of volunteers required for that block. For scenic spots a guide is hired so no volunteers are needed.

A tourist route plan is called feasible if for every two scenic spots there exists a path connecting them such that every block along the path is either a scenic spot or a road block that is assigned volunteers. The task is to choose a set of road blocks (and assign the corresponding volunteers for each chosen block – note that if a road block is used in more than one path, its cost is only counted once) so that all scenic spots become connected and the total number of volunteers is minimized.

You are given the grid description. Compute the minimum total number of volunteers required to achieve such a plan. If there is only one (or no) scenic spot, output 0.

Note: If any formulas are needed, use LaTeX format. For example, the full mask for \(K\) scenic spots is \( (1 \ll K) - 1 \).

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns respectively.

Each of the next \(N\) lines contains \(M\) tokens separated by spaces. A token is either an integer (indicating the required volunteers for that road block) or the character X (indicating a scenic spot).

outputFormat

Output a single integer — the minimum total number of volunteers required such that for any two scenic spots there exists a path connecting them through blocks that are either scenic or have volunteers assigned. If there is only one (or no) scenic spot, output 0.

sample

3 3
X 1 2
3 1 X
4 1 1

2