Printed Circuit

A printed circuit is a board made of nodes and wire segments that join pairs of nodes. Here the nodes form a rectangular grid, and every wire segment connects two adjacent nodes either vertically or horizontally. A circuit is connected when any two nodes are linked through a chain of wire segments.

You are given a circuit in which some adjacent nodes are already joined by wire segments. You must add new wire segments so that the entire circuit becomes connected. A new vertical segment costs $1$ and a new horizontal segment costs $2$.

Figure 1	Figure 2

Write a program that finds a least-cost completion of the circuit and reports two values:

1. $K$, the number of new wire segments used in a least-cost completion; and
2. $V$, the total cost of that completion.

The first line contains two integers $N$ and $M$ ($1 \le N \le 100$, $1 \le M \le 100$): the number of rows and the number of columns of the grid. Nodes are addressed by coordinates; the top-left node is $(1, 1)$ and the bottom-right node is $(N, M)$.

Each of the next $N$ lines contains $M$ integers. The value in row $i$, column $j$ describes the wire segments from node $(i, j)$ toward $(i+1, j)$ (downward) and toward $(i, j+1)$ (rightward):

• $0$: neither the segment $(i, j)$-$(i+1, j)$ nor $(i, j)$-$(i, j+1)$ is present.
• $1$: only the segment $(i, j)$-$(i+1, j)$ is present.
• $2$: only the segment $(i, j)$-$(i, j+1)$ is present.
• $3$: both of those segments are present.

Values that would point outside the grid never occur (for example, only $0$ is valid at $(N, M)$).

Print one line with two integers $K$ and $V$ separated by a space: the number of new wire segments in a least-cost completion, and the total cost of that completion.

Figure 1 shows one such circuit, and Figure 2 shows one of its least-cost completions, which uses $5$ new segments for a total cost of $6$. The completion itself is not unique, but $K$ and $V$ always are.