Giải bài trực tuyến

Ngày nay, khi internet đã trở nên vô cùng phổ biến, các cuộc thi đều có xu hướng chuyển sang hình thức thi on-line, vừa tiết kiệm được chi phí, vừa thu hút được số lượng đông đảo thí sinh. HAOI (Hot Angel On the Internet – tạm dịch là Thiên thần xinh đẹp trên mạng) là một cuộc thi như vậy. Giống như những cuộc thi sắc đẹp bình thường, HAOI cũng bao gồm các vòng thi phụ: tài năng, trí tuệ, trang phục truyền thống… Sau đây là câu hỏi ở phần thi trí tuệ:

Một toà nhà hình chữ nhật được chia thành MxN ô vuông nhỏ. Ở mỗi ô vuông, người ta xây đúng một bức tường là một trong hai đường chéo của ô đó. Yêu cầu tìm đường đi nhanh nhất từ mặt phía Bắc tới mặt phía Nam của toà nhà mà không được đi ra ngoài toà nhà?

Xét ví dụ trong hình vẽ bên, có 3 đường đi khác nhau. Trong đó, đường 1 và 3 là ngắn nhất với độ dài 10.

Giả sử bạn gái của bạn đang tham gia HAOI. Bạn hãy lập trình một chương trình giải quyết câu hỏi trên trong thời gian cho phép để giúp đỡ cô ấy.

Dữ liệu

• Dòng đầu tiên là hai số M, N.
• MxN số tự nhiên tiếp theo (mỗi số cách nhau ít nhất một khoảng trống) miêu tả trạng thái các bức tường ở các ô (1,1), (1,2) … (1,N), (2,1), (2,2) … (M,N). Số 0 nếu bức tường nối đỉnh trái trên với phải dưới, số 1 nếu bức tường nối đỉnh trái dưới và phải trên của ô vuông.

Kết quả

• In ra file HAOI.OUT hai số nguyên là độ dài đường đi ngắn nhất và số lượng đường đi có độ dài như vậy. Trong trường hợp không có đường đi nào, in ra một dòng chứa hai số 0 0.

Giới hạn

1 ≤ M, N ≤ 1000

Ví dụ

Dữ liệu
5 5
0 0 1 1 1 
1 1 0 0 0
0 0 1 1 1
1 1 0 0 0
0 0 0 1 1	

Kết quả
10 2