Một mảng mạch in là các node và các đoạn dây nối giữa các cặp node. Chúng ta quan tâm đến một loại mạch in đặc biệt mà các node được xếp trong một lưới chữ nhật và các đoạn dây chỉ nối các node kề nhau (theo chiều dọc hoặc ngang). Một mạch in gọi là kết nối được nếu 2 node bất kì khác nhau đều được liên kết với nhau bởi một chuỗi các đoạn dây. Cho một mạch in trong đó một số node kề nhau đã được nối. Bạn phải thêm vào các dây mới để cho mạch in được liên kết. Giá của một mạch in là 1 nếu nó là mạch đứng và 2 nếu nó là mạch ngang.

Yêu cầu: Bạn hãy viết chương trình:

1. Xác định số cạnh mới nối thêm
2. Tính giá tiền ít nhất để nối mạch

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên N và M là số các hàng và số các cột trong lưới (0<N,M<100). Các node của mạch được xác định bằng toạ độ của nó, node trên trái là (1,1) và node phải dưới là (N,M).
• Mỗi dòng trong số N số tiếp theo chứa M số nguyên. Số trong hàng i, cột j diễn tả các đoạn dây giữa cặp node (i,j) và (i+1,j) và cũng giữa cặp (i,j) và (i,j+1) theo cách sau:

• 0: cả cặp (i,j); (i+1,j) và cặp (i,j); (i,j+1) không có dây nối.
• 1: chỉ có cặp (i,j); (i+1,j) được nối.
• 2: chỉ có cặp (i,j); (i,j+1) được nối.
• 3: cả hai cặp được nối.

Kết quả:  ghi 2 số K và U trên 1 dòng là số đoạn dây mới thêm và tổng số tiền ít nhất tìm được.

Ví dụ:

Inp2:

12 20
1 2 1 3 1 3 3 0 0 2 1 2 3 0 2 1 3 3 3 1
0 0 0 0 1 3 0 1 1 3 0 0 0 3 1 0 1 0 0 0
2 2 3 0 3 1 3 0 2 0 1 2 2 0 0 3 1 2 1 1
1 2 2 3 3 1 3 1 2 1 0 3 2 1 1 1 3 0 3 0
1 2 3 0 3 2 0 3 3 2 3 1 1 3 3 3 0 3 1 0
2 1 2 1 3 3 1 3 1 2 0 3 0 3 2 3 1 2 2 0
2 2 1 1 0 1 0 1 1 3 0 2 0 0 2 3 0 1 0 1
3 3 1 1 3 1 1 3 2 2 2 0 3 2 1 1 1 1 0 1
0 0 3 3 3 2 1 0 2 3 0 0 3 1 3 3 3 1 1 1
1 2 1 3 0 3 2 2 2 3 1 1 0 1 2 2 0 3 2 1
1 2 0 3 3 0 0 1 2 3 0 3 1 2 2 3 3 3 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Out2: 29 29