Công ty AZ đang sản xuất robot vận chuyển hàng hóa tự động trên mặt đất. Để làm việc đó, AZ tiến hành huấn luyện robot trên một địa hình phẳng được chia thành một lưới các ô vuông gồm \(m\) dòng (đánh số từ \(1\) đến \(m\)) và \(n\) cột (đánh số từ \(1\) đến \(n\)). Ô nằm giao giữa dòng \(i\), cột \(j\) được gọi là ô \((i, j)\) và chứa số nguyên dương \(c_{ij}\).

Robot có kích thước bằng đúng một ô vuông. Ban đầu, robot đang ở ô \((1, 1)\), robot có thể di chuyển sang ô \((1, 2)\) hoặc ô \((2, 1)\). Sau bước di chuyển đầu tiên, số lần robot rẽ trái sẽ được kiểm soát. Robot cần tìm đường đi đến ô \((m, 1)\) theo quy tắc: tại mỗi ô, robot có thể di chuyển sang ô chung cạnh với ô đó, không được đi ra ngoài bảng và số lần rẽ trái không vượt quá \(k\). Việc đánh giá cho điểm một đường đi được dựa trên số lượng số \(0\) liên tiếp nằm ở cuối của tích các số trong các ô thuộc đường đi, số lượng số \(0\) càng ít thì càng được đánh giá cao.

Yêu cầu: Cho bảng số, tìm đường đi có số lượng số \(0\) liên tiếp nằm ở cuối của tích các số trong ô thuộc đường đi là ít nhất.

Input

• Dòng đầu tiên chứa ba số nguyên \(m, n, k\) (\(k \le 30\)).
• \(m\) dòng tiếp theo, mỗi dòng \(n\) số nguyên dương mô tả bảng số \(c_{ij}\).

Output

• Đưa ra một số nguyên duy nhất là số lượng số \(0\) liên tiếp nằm ở cuối của tích các số trong các ô thuộc đường đi tìm được.

Example

5 5 1
1  1  1  1  1
20 20 20 20 1
1  1  1  10 1
1  20 1  20 1
5  20 1  1  1

1

Constraints

• \(m, n \le 300\).
• \(k \le 30\).
• \(c_{ij} \le 10^9\).
• Có \(30\%\) số điểm có \(m, n \le 30\) và \(c_{ij}\) có dạng \(10^p\) (\(p \le 9\)).
• Có \(30\%\) số điểm khác có \(m, n \le 30\) và \(c_{ij} \le 10^9\).
• Có \(40\%\) số điểm còn lại có \(m, n \le 300\) và \(c_{ij} \le 10^9\).

Nguồn: 3D '1920