题目描述

月立志要做一个合格的女仆。

这天晚上月要关掉楼里所有的灯。这个楼有n层，每层有m个房间，每层的两侧有楼梯，只能从楼梯上下楼。每个房间里的灯开关状态由一个大小为n*(m+2){包括两边的楼梯}的01矩阵表示，0代表关着的，1代表开着的。每次向左或者向右移动一格会消耗一分钟，从楼梯上下楼也会消耗一分钟，但是走到房间里关灯不需要消耗时间。一开始月在矩阵左下角，现在她想知道她最少需要多少分钟才能把所有的灯全部关上。

输入格式

第一行包含两个正整数n,m，表示楼有n层，每层m个房间。

接下来n行每行m+2个整数，表示这一层m个房间的状态。注意楼梯的部分始终是0。

输出格式

一行一个整数表示答案。

样例输入

3 4
001000
000010
000010

样例输出

12

数据范围

对于30%的数据，n*m<=12

对于100%的数据，n<=8,m<=100。