Xoắn ốc

Trên một lưới kích thước $N \times M$ ô vuông đơn vị, người ta đặt một quân cờ vào ô trên cùng bên trái. Các ô được điền số từ 1 đến $N \times M$ theo mô hình xoắn ốc, bắt đầu từ ô trên cùng bên trái và hướng sang phải.
Trên lưới, mỗi ô hoặc có màu đen hoặc màu trắng. Ô màu đen hiển thị một hố đen, không thể di chuyển quân cờ vào ô này. Ô màu trắng biểu thị một vị trí hợp lệ, có thể di chuyển quân cờ vào ô này.
Với một số nguyên $K$ cho trước, bạn cần tìm cách di chuyển quân cờ đến ô được đánh số $N \times M$ bằng cách thực hiện một số bước di chuyển như sau: “giả sử quân cờ đang ở ô ghi số $x$ thì bạn có thể di chuyển nó vào một trong các ô ghi số $x + 1, x + 2, \dots, x + K$ với điều kiện ô đó phải có màu trắng”.
Hãy lập trình xác định hai thông tin sau:

• Cần thực hiện ít nhất bao nhiêu bước để di chuyển quân cờ đến ô được đánh số $N \times M$?
• Gọi $F(i)$ là số cách di chuyển hợp lệ khi quân cờ đang ở ô màu trắng được đánh số $i$, hãy tính giá trị: $\max(F(1), F(2), \dots, F(N \times M))$.

Hình dưới minh họa một bàn cờ với $N = 4,\ M = 5$. Với $K = 4$, từ ô có số 13 ta có thể đưa quân cờ đến ô có số 15 hoặc 17 nên $F(13) = 2$.

• Dòng 1: Chứa ba số nguyên $N, M, K$;
• Tiếp theo là $N$ dòng, mỗi dòng chứa $M$ số nguyên 0 hoặc 1 mô tả lưới. Với số 0 đại diện cho ô màu trắng, số 1 đại diện cho ô màu đen.

• Ghi trên một dòng gồm hai số nguyên $P, Q$ là hai thông tin tìm được. $P$ là số bước di chuyển tối thiểu để quân cờ đến được ô được đánh số $N \times M$, $Q$ là giá trị $\max(F(1), F(2), \dots, F(N \times M))$. Nếu không có cách đưa quân cờ đến ô được đánh số $N \times M$ thì $P = -1$.

• Subtask 1: 19% điểm có $N = 1,\ M \le 30000;\ K \le 100$;
• Subtask 2: 13% điểm có $N = 1,\ M \le 100000,\ K \le 100000$;
• Subtask 3: 18% điểm có $N \le 200,\ M \le 3000,\ K \le 50$;
• Subtask 4: 50% điểm có $N \le 200,\ M \le 30000,\ K \le 6000000$.