Description
有些人离开教室时，不关灯，浪费电。LGDdp等所有的学生和老师离开教学楼后，把所有的灯关掉。
该建筑由n层。每层楼有m间房间，最左、最右有楼梯。换句话说，建筑物可以表示为一个有n行m + 2列的矩形，第一列和最后一列代表楼梯，而中间的m列代表房间。
LGDdp站在第一层的左边楼梯。他想把所有的灯都关掉。他所站的这层上的所有灯都熄灭后，他才能再上楼。LGDdp需要一分钟的时间使用楼梯去下一个楼层，或者从当前的房间/楼梯移动到同一楼层的相邻房间/楼梯。关灯不花时间，移动花时间。LGDdp忙着刷题，机智的你能帮他找到关闭所有灯的最少时间吗？
请注意，LGDdp不必回到他的起始位置。

Input
第一行包含两个整数n和m（1≤n≤15和1≤m≤100） - 分别是每层的层数和房间数量。
接下来的n行包含建筑描述。每行包含长度为m + 2的二进制字符串，表示一个楼层（左侧楼梯，然后m个房间，然后右侧楼梯），其中0表示灯熄灭，1表示灯已亮。楼层从上到下排列，最后一行代表底层。
每个字符串的第一个和最后一个字符分别代表左边和右边的楼梯，所以它们总是0。

Output
一个整数 - 关闭所有灯光所需的最短总时间。

Sample Input
2 2
0010
0100
3 4
001000
000010
000010
4 3
01110
01110
01110
01110

Sample Output
5
12
18

HINT
在第一个例子中，LGDdp将进入底层的房间，然后他将使用左侧或右侧的楼梯进入二楼的房间。

在第二个例子中，他将去到底层的房间，使用右边的楼梯，去第二层的房间，再次使用右边的楼梯，然后去到最后一层的房间。

在第三个例子中，S型走位。