인쇄 회로

인쇄 회로(printed circuit) 는 노드(node) 와, 노드 쌍을 잇는 배선(wire segment) 으로 이루어진 기판이다. 이 문제에서 노드는 직사각형 격자 형태로 배열되며, 모든 배선은 인접한 두 노드를 세로 또는 가로로만 연결한다. 임의의 두 노드가 배선의 연쇄로 이어져 있으면 그 회로는 연결되어 있다(connected) 고 한다.

일부 인접한 노드들이 이미 배선으로 연결된 회로가 주어진다. 전체 회로가 연결되도록 새로운 배선을 추가해야 한다. 새 세로 배선의 비용은 $1$, 새 가로 배선의 비용은 $2$이다.

그림 1	그림 2

최소 비용으로 회로를 완성하는 프로그램을 작성하여 다음 두 값을 구하라.

1. 최소 비용 완성에 사용된 새 배선의 개수 $K$.
2. 그 완성의 총 비용 $V$.

첫 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N \le 100$, $1 \le M \le 100$). $N$은 격자의 행 수, $M$은 열 수이다. 노드는 좌표로 지칭하며, 왼쪽 위 노드가 $(1, 1)$, 오른쪽 아래 노드가 $(N, M)$이다.

이어지는 $N$개의 줄에는 각각 $M$개의 정수가 주어진다. $i$행 $j$열의 값은 노드 $(i, j)$에서 $(i+1, j)$ 방향(아래쪽) 및 $(i, j+1)$ 방향(오른쪽)으로의 배선을 다음과 같이 나타낸다.

• $0$: 배선 $(i, j)$-$(i+1, j)$와 $(i, j)$-$(i, j+1)$이 모두 없다.
• $1$: 배선 $(i, j)$-$(i+1, j)$만 있다.
• $2$: 배선 $(i, j)$-$(i, j+1)$만 있다.
• $3$: 두 배선이 모두 있다.

격자 밖을 가리키는 값은 주어지지 않는다 (예를 들어 $(N, M)$에서는 $0$만 유효하다).

한 줄에 두 정수 $K$와 $V$를 공백으로 구분하여 출력한다. $K$는 최소 비용 완성에 사용된 새 배선의 개수, $V$는 그 완성의 총 비용이다.

그림 1은 하나의 회로를, 그림 2는 그 회로의 한 최소 비용 완성을 보여준다. 이 완성은 새 배선 $5$개를 사용해 총 비용 $6$을 이룬다. 완성 방법 자체는 유일하지 않지만 $K$와 $V$는 항상 유일하다.