Description

        为了将这些生产的玩具销往海外，晚上江北的玩具公司灯火通明。安安是公司的保安，当所有工作人员离开公司后，他要把公司里所有的门都关闭。房间的门有些是关闭的，有些是打开的。为了察看该公司里所有房间的门是否关闭，该公司安装了物联网智能门禁检测器，在保安配备的设备中会显示哪些房间的门已经关闭，哪些房间的门还是打开的。
        该公司共有 x 层，每层楼各有 y 个房间，每层楼的最左边和最右边各有一个楼梯。也就是说，这家公司可以表示为 x 行和 y+2 列的矩形，其中第一列和最后一列表示楼梯，中间 y列表示房间。（注意：最左边的是第一列楼梯）保安安安目前站在一楼的第一列的楼梯处。他必须一个房间一个房间去关门（注：关门在瞬间完成，所以关门时间可忽略不计），但安安可用 1 单位时间完成以下内容之一：爬楼梯到达上一层楼，从房间到达相邻的房间或楼梯，从楼梯到达相邻的房间（也就是说向上、向左、向右“走一格”各需要 1 单位时间）。请你帮助安安计算关闭所有门的最短的单位时间。
        特别提醒：安安是从最下面一层的第一列的楼梯处出发，他不必回到起始位置，并且他不用访问已经关门的房间。当所有房门都提示关闭时，他的任务就完成了。

Input Format

        第一行输入两个整数 x 和 y,分别表示总共的楼层数和每层的房间数。
        下面的 x 行,每行输入 y + 2 个二进制的字符串，依次表示某个楼层的左楼梯，y 个房间，右楼梯，其中 0 表示门是关闭的，1 表示门是打开的。楼层是从下往上递增的，因此最后一行代表底层（就是第一层）。
        每行字符串的第一个和最后一个字符分别表示左侧楼梯和右侧楼梯，所以它们始终为 0。

Output Format

输出一个整数，表示将所有门都关闭的最短时间。

2 2
0010
0100

5

Hint

样例输入 Copy
【样例1】
2 2 
0010 
0100 
【样例2】
3 4 
001000 
000010 
000010 
【样例3】
4 3 
01110 
01110 
01110 
01110 
样例输出 Copy
【样例1】
5
【样例2】
12
【样例3】
18
 
提示
样例一：安安先到达第一层楼的第一个房间，然后他可以使用左右两侧的楼梯到达第二层楼的第二个房间，看看使用哪个楼梯到达的时间最短，此样例使用左右两侧的楼梯的时间都相同。
样例二：安安先到达第一层楼的第四个房间，使用右侧楼梯到达第二层楼的第四个房间，再使用右侧楼梯，最后到达第三层楼的第二个房间。 
样例三：他将走过所有的房间，在每层楼的左右楼梯之间交替。 

1<=x<=15 且 1<=y<=100 

Source

动态规划