Problem
اریک به عنوان نگهبان در دانشگاه کار می کند، بنابراین پس از یک روز کار در ساختمان قدم می زند و شب ها چراغ ها را خاموش می کند.
این ساختمان دارای n طبقه و دو راه پله در سمت چپ و راست است. در امتداد راهرویی که پله های چپ و راست را به هم متصل می کند، در هر طبقه متر اتاق وجود دارد. به عبارت دیگر، ساختمان را می توان به صورت یک مستطیل با n ردیف و m + 2 ستون نشان داد که ستون اول و آخر — پله ها و m ستون در وسط — اتاق ها.
اریک اکنون در طبقه اول روی پله های سمت چپ ایستاده است. او می‌خواهد چراغ‌ها را همه جا خاموش کند، در حالی که نمی‌خواهد قبل از خاموش کردن همه چراغ‌های طبقه فعلی به طبقه بالا برود. البته اریک باید در اتاق باشد تا چراغ ها را خاموش کند. اریک یک دقیقه را صرف راه رفتن از پله های یک طبقه یا رفتن به اتاق بعدی/پله های اتاق بعدی یا پله های همان طبقه می کند. خاموش کردن چراغ‌های اتاقی که اریک در آن است وقت او را نمی‌گیرد.
به اریک کمک کنید حداقل زمان را برای خاموش کردن همه چراغ‌های ساختمان پیدا کند.
توجه داشته باشید که اریک مجبور نیست به موقعیت اصلی خود بازگردد و همچنین لازم نیست از اتاق هایی که چراغ ها در آن خاموش هستند بازدید کند.
ورودی:
خط اول شامل دو عدد صحیح n و m (1 ≤ n ≤ 15، 1 ≤ m ≤ 100) — تعداد طبقات و تعداد اتاق های هر طبقه به ترتیب.
n خط بعدی شامل توضیحاتی از ساختمان است. هر خط شامل یک رشته صفر و یک به طول m + 2 است که یک طبقه را توصیف می‌کند (پله‌های چپ، سپس m اتاق، سپس پله‌های راست)، جایی که 0 به معنای خاموش بودن چراغ‌ها و 1 به معنای روشن بودن چراغ‌ها است. طبقات به ترتیب از بالا به پایین آورده شده است، به ویژه، خط آخر طبقه اول را توصیف می کند.
اولین و آخرین کاراکتر هر خط پله ها را توصیف می کند، بنابراین آنها همیشه 0 هستند.
خروجی:
چاپ یک عدد — حداقل زمان ممکن برای خاموش کردن همه چراغ ها.
مثال:
<بدن>
| ورودی |
خروجی |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
توضیحات:
در مثال اول، اریک ابتدا به اتاق 1 در طبقه اول و سپس — به اتاق 2 در طبقه دوم با استفاده از هر نردبان.
در مثال دوم، او ابتدا به اتاق چهارم در طبقه اول می رود، یک طبقه از پله های سمت راست بالا می رود، وارد اتاق چهارم در طبقه دوم می شود، دوباره از پله های سمت راست بالا می رود، به طبقه دوم می رود. اتاق در طبقه آخر.