有些人离开工作场所时开着灯,这是浪费资源。作为 DHBW 的一名 hausmeister,Sagheer 等到所有学生和教授都离开大学大楼后,才去关掉所有的灯。
该建筑由 n 层组成,左右两侧有楼梯。每层有m个房间,在同一条线上,有一条连接左右楼梯的走廊经过所有房间。换句话说,建筑物可以表示为一个 n 行 m + 2 列的矩形,其中第一列和最后一列代表楼梯,中间的 m 列代表房间。
Sagheer 站在底层左侧楼梯处。他想关掉所有的灯,这样他就不会上楼,直到他所站的楼层的所有灯都关掉为止。当然,萨吉尔必须去一个房间才能关掉那里的灯。萨吉尔需要一分钟时间才能使用楼梯到达下一层,或者从当前房间/楼梯移动到同一楼层的相邻房间/楼梯。他很快就关掉了他当前所在房间的灯。帮助 Sagheer 找到关闭所有灯的最短总时间。
请注意,Sagheer 不必返回其起始位置,也不必访问灯已关闭的房间。
输入
第一行包含两个整数 n 和 m(1 ≤ n ≤ 15 和 1 ≤ m ≤ 100)——分别是楼层数和每层房间数。
接下来的 n 行包含建筑物描述。每行包含一个长度为 m + 2 的二进制字符串,表示楼层(左边的楼梯,然后是 m 个房间,然后是右边的楼梯),其中 0 表示灯关闭,1 表示灯打开。楼层从上到下列出,因此最后一行代表底层。
每个字符串的第一个和最后一个字符分别代表左楼梯和右楼梯,因此它们始终为 0。
输出
打印一个整数——关闭所有灯所需的最短总时间。
示例
输入 #1
2 2 0010 0100
输出 #1
5
输入 #2
3 4 001000 000010 000010
输出 #2
12
输入 #3
4 3 01110 01110 01110 01110
输出 #3
18
注意
在第一个示例中,Sagheer 将前往一楼的房间 1,然后他将使用左侧或右侧的楼梯前往二楼的房间 2。
在第二个示例中,他将前往一楼的第四个房间,使用右侧的楼梯,前往二楼的第四个房间,再次使用右侧的楼梯,然后前往最后一层的第二个房间。
在第三个示例中,他将在每个楼层的左右楼梯之间交替走过整个走廊。