Sơ tán

Một trạm nghiên cứu là một lưới ô vuông kích thước $n\times n$, mỗi ô có kích thước $1\times 1$. Mỗi ô hoặc là một lò phản ứng, hoặc là một phòng thí nghiệm.

Trong lưới, ký tự mô tả từng ô như sau:

• Ký tự Y: một lò phản ứng đang hoạt động bình thường.
• Ký tự Z: lò phản ứng bị hỏng (có đúng một ô như vậy trên toàn trạm).
• Chữ số 0–9: một phòng thí nghiệm.

Các lò phản ứng là ô không thể đi qua. Người ta chỉ có thể di chuyển giữa các phòng thí nghiệm. Giữa hai phòng thí nghiệm nằm ở hai ô kề cạnh (chung một cạnh) luôn có một hành lang nối chúng.

Trạm được mô tả bằng hai lưới cùng kích thước:

• Lưới thứ nhất mô tả số nhà khoa học: tại một ô phòng thí nghiệm, chữ số là số nhà khoa học đang có mặt ở đó.
• Lưới thứ hai mô tả số khoang cứu hộ: tại một ô phòng thí nghiệm, chữ số là số khoang cứu hộ ở đó. Mỗi khoang chỉ chứa được tối đa một nhà khoa học; một khi nhà khoa học vào được khoang thì coi như đã được cứu.

Vị trí các lò phản ứng trong hai lưới trùng khớp nhau.

Sự lan của chất làm mát. Ô chứa lò phản ứng hỏng (Z) được coi là bị nhiễm độc ngay tại phút $0$. Mỗi phút, chất làm mát lan qua các hành lang: nếu tại một thời điểm nào đó một ô đang bị nhiễm độc, thì sang phút tiếp theo tất cả các phòng thí nghiệm kề cạnh với nó cũng bị nhiễm độc. Chất làm mát không lan qua ô lò phản ứng. Khi một phòng thí nghiệm bị nhiễm độc, mọi nhà khoa học ở đó mà chưa vào khoang cứu hộ đều thiệt mạng.

Di chuyển. Còn đúng $t$ phút nữa là trạm phát nổ. Trong mỗi phút, một nhà khoa học có thể đi theo một hành lang sang phòng thí nghiệm kề bên nếu ô đó chưa bị nhiễm độc. Trên mỗi hành lang, số nhà khoa học di chuyển đồng thời (theo cả hai chiều) là không giới hạn. Nhà khoa học luôn kịp thực hiện hành động của mình (di chuyển sang phòng kế tiếp, hoặc trèo vào khoang cứu hộ) trước khi phòng thí nghiệm đang đứng bị nhiễm độc.

Hãy tìm số nhà khoa học tối đa có thể được cứu.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $t$.
• $n$ dòng tiếp theo, mỗi dòng $n$ ký tự, mô tả vị trí các nhà khoa học.
• Tiếp theo là đúng một dòng trống.
• $n$ dòng tiếp theo, mỗi dòng $n$ ký tự, mô tả vị trí các khoang cứu hộ.

Dữ liệu ra

In ra một số nguyên duy nhất: số nhà khoa học tối đa có thể tự cứu mình.

Ràng buộc

• $2\le n\le 10$
• $1\le t\le 60$
• Có đúng một ô Z trên toàn trạm.
• Vị trí các lò phản ứng trong hai lưới trùng khớp nhau.

Ví dụ