暂无测试数据。

Background

杭二白马湖OJ上的题目
http://115.236.186.99:8080/JudgeOnline/
但是如需要杭州二中的账号请私信所在管理员

Description

已知公路总长L米,一共有K个赛道,你的赛车总是和公路上其他的普通的车走相反的方向,并且所有的车每秒沿赛道行驶1m(具体看图)
问题是:跑到终点最少撞多少次车?
我们简化一下模型,画一个长为(L+1)宽为K的网格,设所有的车都是点,并且每秒末都会出现在这个网格的某个顶点上.公路上其他的车都以固定的1m/s的速度自上而下行驶,而你的跑车自下而上行驶,并且每秒可以从一个点行驶到它上方\左上方\右上方的点(假设飘移不浪费时间,具体请看图).

我们假设,撞车不会使车损坏,不会使车减速
对于撞车的设定:当每秒末你的车和另外一辆车处在同一点上时,算撞车;你的车和另一辆车迎面开过来,算撞车.具体请看下图:*

Format

Input

nfs.in 首行两个数,L,K,表示赛道距离,以及有几个赛道.
接下来L行,每行K个字符,第i行第j个字符表示公路距终点距离为i-1的第j个赛道的初始状态:0表示该点没有车,1表示该点有车.
铭记一点:初始时你的车在第L+1行,你可以指定一个第L+1行的位置为你的车的初始位置,而第L+1行是不在输入文件里的.

Output

nfs.out
一个数ans,表示最少撞车次数

Sample 1

Input

4  4
1000
0100
0001
0000

Output

0

Sample 2

Input

6  4
1111
1111
1111
0000
1111
0000

Output

3

Sample 3

Input

4  4
1111
1111
1111
1111

Output

2

Limitation

1s, 1024KiB for each test case.

Hint

【对样例2的说明】
初始 第一秒 第二秒 第三秒
距终点0m 1111
距终点1m 1111 1111
距终点2m 1111 1111 1111
距终点3m 0000 1111 1111 1P11
距终点4m 1111 0000 P111 1111
距终点5m 0000 P111 0000 1111
距终点6m C
C代表该点只有你的车,P代表该点既有你的车又有其他的车.最优方案为第一秒直走,与一辆车相撞,第二秒直走,又与一辆车相撞,第三秒斜向右走,又与一辆车相撞,总共3次.如果第3秒直走,将与2辆车相撞,那么就撞了4次,所以3次最优.
【对样例3的说明】
不停地斜着走
【数据范围】
对于60%的数据1<=n<=5 <1=k<=5
对于100%的数据1<=n<=100,1<=k<=10