有些人在离开工作场所时把灯开着，这是一种资源浪费。作为DHBW的管理员，Sagheer等到所有学生和教授离开大学建筑物，然后去关掉所有的灯。

建筑物由n层组成，左右两侧有楼梯。每层有m个沿着同一线的房间，房间之间有连接左右楼梯的走廊。换句话说，建筑物可以表示为一个有n行m + 2列的矩形，第一列和最后一列代表楼梯，中间的m列代表房间。

Sagheer站在左侧楼梯的底层。他希望关掉所有的灯，但在上楼之前不会离开所在楼层的房间。当然，Sagheer必须进入一个房间才能关掉灯。Sagheer通过楼梯上楼或者在同一楼层的相邻房间/楼梯间移动，每次移动到下一个楼层或相邻房间/楼梯间需要一分钟。在当前位置关掉房间里的灯不需要时间。帮助Sagheer找到关掉所有灯所需的最短总时间。

请注意，Sagheer不必回到起始位置，也不必进入已经关掉灯的房间。

输入 第一行包含两个整数n和m（1 ≤ n ≤ 15和1 ≤ m ≤ 100）—楼层数和每层的房间数。

接下来的n行包含建筑物的描述。每行包含一个长度为m + 2的二进制字符串，表示一层（左侧楼梯，然后m个房间，然后右侧楼梯），其中0表示灯已关闭，1表示灯已打开。楼层从顶层到底层列出，因此最后一行代表底层。

每个字符串的第一个和最后一个字符代表左侧和右侧楼梯，因此它们总是0。

输出 输出一个整数—关掉所有灯所需的最短总时间。

示例

1.Inputcopy
2 2
0010
0100
1.Outputcopy
5

2.Inputcopy 3 4
001000
000010
000010
2.Outputcopy
12

3.Inputcopy
4 3
01110
01110
01110
01110
3.Outputcopy
18

注意
在第一个示例中，Sagheer将前往底层的第1个房间，然后使用左侧或右侧楼梯前往第二层的第2个房间。

在第二个示例中，他将前往底层的第四个房间，使用右侧楼梯，前往第二层的第四个房间，再次使用右侧楼梯，然后前往最后一层的第二个房间。

在第三个示例中，他将穿过整个走廊，每层交替使用左侧和右侧楼梯。