Problem
Eric làm bảo vệ tại trường đại học nên sau một ngày làm việc, anh ấy đi dạo quanh tòa nhà và tắt đèn vào ban đêm.
Tòa nhà có n tầng và hai cầu thang bên trái và bên phải. Có m phòng trên mỗi tầng dọc theo hành lang nối cầu thang trái và phải. Nói cách khác, tòa nhà có thể được biểu diễn dưới dạng hình chữ nhật có n hàng và m + 2 cột, trong đó cột đầu tiên và cột cuối cùng — cầu thang và m cột ở giữa — phòng.
Eric hiện đang đứng ở tầng một trên cầu thang bên trái. Anh ta muốn tắt đèn ở mọi nơi, trong khi anh ta không muốn lên tầng trên trước khi tắt tất cả đèn ở tầng hiện tại. Tất nhiên, Eric phải ở trong phòng để tắt đèn. Eric dành một phút để đi bộ lên cầu thang một tầng hoặc đi sang phòng/cầu thang từ phòng bên cạnh hoặc cầu thang trên cùng một tầng. Việc tắt đèn trong phòng Eric đang ở không làm mất thời gian của anh ấy.
Giúp Eric tìm thời gian tối thiểu để tắt tất cả đèn trong tòa nhà.
Lưu ý rằng Eric không phải quay lại vị trí ban đầu của mình và anh ấy cũng không bắt buộc phải vào các phòng đã tắt đèn.
Đầu vào:
Dòng đầu tiên chứa hai số nguyên n và m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — lần lượt là số tầng và số phòng mỗi tầng.
n dòng tiếp theo mô tả tòa nhà. Mỗi dòng chứa một chuỗi số 0 và hàng đơn vị có độ dài m + 2 mô tả một tầng (cầu thang bên trái, sau đó là m phòng, rồi đến cầu thang bên phải), trong đó 0 có nghĩa là đèn tắt và 1 có nghĩa là đèn đang bật. Các tầng được cho theo thứ tự từ trên xuống dưới, đặc biệt, dòng cuối cùng mô tả tầng một.
Ký tự đầu tiên và cuối cùng của mỗi dòng mô tả cầu thang, vì vậy chúng luôn là 0.
Đầu ra:
In một số — thời gian tối thiểu có thể cần thiết để tắt tất cả các đèn.
Ví dụ:
| Đầu vào |
Đầu ra |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Giải thích:
Trong ví dụ đầu tiên, trước tiên Eric sẽ đến phòng 1 ở tầng một, sau đó — lên phòng 2 trên tầng hai bằng thang bất kỳ.
Trong ví dụ thứ hai, trước tiên anh ta sẽ đi đến phòng thứ tư ở tầng một, đi lên một tầng ở cầu thang bên phải, vào phòng thứ tư ở tầng hai, lại đi lên cầu thang bên phải, đi đến tầng thứ hai phòng ở tầng cuối cùng.