Problem
Eric bekerja sebagai pengawal keselamatan di universiti, jadi selepas seharian bekerja dia berjalan di sekitar bangunan dan menutup lampu pada waktu malam.
Bangunan ini mempunyai n tingkat dan dua tangga di kiri dan kanan. Terdapat m bilik di setiap tingkat di sepanjang koridor yang menghubungkan tangga kiri dan kanan. Dalam erti kata lain, bangunan itu boleh diwakili sebagai segi empat tepat dengan n baris dan m + 2 lajur, di mana lajur pertama dan terakhir — tangga, dan m lajur di tengah — bilik.
Eric kini berdiri di tingkat satu di tangga kiri. Dia mahu menutup lampu di mana-mana, sedangkan dia tidak mahu naik ke lantai atas sebelum menutup semua lampu di lantai sekarang. Sudah tentu, Eric mesti berada di dalam bilik untuk menutup lampu. Eric meluangkan masa satu minit untuk menaiki tangga satu tingkat atau pergi ke bilik/tangga sebelah dari bilik sebelah atau tangga di tingkat yang sama. Mematikan lampu di dalam bilik Eric tidak mengambil masa.
Bantu Eric mencari masa minimum untuk mematikan semua lampu di dalam bangunan.
Ambil perhatian bahawa Eric tidak perlu kembali ke kedudukan asalnya, dan juga bahawa dia tidak perlu melawat bilik yang lampu sudah mati.
Input:
Baris pertama mengandungi dua integer n dan m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — bilangan tingkat dan bilangan bilik pada setiap tingkat, masing-masing.
N baris seterusnya mengandungi penerangan tentang bangunan. Setiap baris mengandungi rentetan sifar dan satu panjang m + 2 menerangkan satu tingkat (tangga kiri, kemudian m bilik, kemudian tangga kanan), dengan 0 bermakna lampu padam dan 1 bermakna lampu menyala. Lantai diberikan mengikut urutan dari atas ke bawah, khususnya, baris terakhir menerangkan tingkat pertama.
Aksara pertama dan terakhir setiap baris menerangkan tangga, jadi mereka sentiasa 0.
Output:
Cetak satu nombor — masa minimum yang mungkin diperlukan untuk mematikan semua lampu.
Contoh:
| Input |
Output |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Penjelasan:
Dalam contoh pertama, Eric akan mula-mula pergi ke bilik 1 di tingkat satu, dan kemudian — ke bilik 2 di tingkat dua menggunakan mana-mana tangga.
Dalam contoh kedua, dia akan pergi dahulu ke bilik keempat di tingkat satu, naik satu tingkat di tangga kanan, masuk bilik keempat di tingkat dua, naik tangga kanan semula, pergi ke kedua. bilik di tingkat terakhir.