Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off.

The building consists of n floors with stairs at the left and the right sides. Each floor has m rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with n rows and m + 2 columns, where the first and the last columns represent the stairs, and the m columns in the middle represent rooms.

Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.

Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 15 and 1 ≤ m ≤ 100) — the number of floors and the number of rooms in each floor, respectively.

The next n lines contains the building description. Each line contains a binary string of length m + 2 representing a floor (the left stairs, then m rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.

The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.


-----Output-----

Print a single integer — the minimum total time needed to turn off all the lights.


-----Examples-----
Input
2 2
0010
0100

Output
5

Input
3 4
001000
000010
000010

Output
12

Input
4 3
01110
01110
01110
01110

Output
18



-----Note-----

In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.

In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.

In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.

Difficulty: interview

Starter code:

Solutions:
n, m = list(map(int, input().split()))
m += 2
l = []
do = False
for i in range(n):
	s = input().strip()
	if s.find('1') != -1 or do:
		do = True
		l.append(s)
n = len(l)
if n == 0:
	print(0)
	return


dp = []
for i in range(n):
	dp.append([None] * 2)

for i in range(n):
	R = 0
	for j in range(m):
		if l[i][j] == '1':
			R = j
	L = m - 1
	for j in range(m - 1, -1, -1):
		if l[i][j] == '1':
			L = j
	if i == 0:
		dp[0][0] = R
		dp[0][1] = (m - 1 - L)
	else:
		dp[i][0] = min(dp[i - 1][0] + 2 * R, dp[i - 1][1] + (m - 1)) + 1
		dp[i][1] = min(dp[i - 1][0] + (m - 1), dp[i - 1][1] + 2 * (m - 1 - L)) + 1
# print(dp)
print(dp[-1][0])


def variant(cur):
    nonlocal minv
    if len(cur) < len(rooms):
        variant(cur + [0])
        variant(cur + [1])
    else:
        curpos = 0
        time = 0
        for i in range(len(rooms) - 1):
            if curpos != cur[i]:
                time += m + 1
                curpos = cur[i]
            else:
                time += 2 * rooms[i][curpos]
            if i != 0:
                time += 1
        time += rooms[-1][curpos] + 1
        if len(rooms) == 1:
            time -= 1
        minv = min(minv, time)



n, m = map(int, input().split())
minv = 1000000000
rooms = []
stopdel = False

for i in range(n):
    line = input()
    a = 0
    for j in range(m + 2):
        if line[j] == '1':
            a = m + 1 - j
            break
    b = 0
    for j in range(m + 1, -1, -1):
        if line[j] == '1':
            b = j
            break
    if a != 0 or b != 0 or stopdel:
        rooms.append((b, a))
        stopdel = True

rooms = rooms[::-1]

if not rooms:
    print('0')
else:
    variant([])
    print(minv)

def sol():

    n, m = map(int, input().split(' '))

    mapp = []

    for a in range(n):
        s = list(input())
        s = [c == "1" for c in s]
        mapp.insert(0, s[1:-1])

    res = None
    #print(mapp)

    empty_floor = n
    while True:
        litup = False
        for x in mapp[empty_floor-1]:
            if x:
                litup = True
                break
        if not litup:
            empty_floor -= 1
        else:
            break
        if empty_floor < 0:
            break

    if empty_floor <= 0:
        return 0

    #print("empty_floor", empty_floor)

    for comb in range(2**(empty_floor-1)):
        temp = 0
        c = bin(comb)[2:]
        c = "0" * ((empty_floor-1)-len(c)) + c
        c = list(c)
        c = [x == "1" for x in c]

        #print("c", c)

        last = False # start from left
        if empty_floor != 1:
            for i, x in enumerate(c):
                if x != last:
                    temp += m+1 + 1
                else:
                    f = None
                    #print(i)
                    #print("last", last)
                    for j, y in enumerate(mapp[i]):
                        if y:
                            f = j
                            if last:
                                break
                    if f is None:
                        temp += 1
                    else:
                        if last:
                            temp += 2 * (m - f) + 1
                        else:
                            temp += 2 * (f + 1) + 1
                last = x


        #final floor:
        f = None
        for j, y in enumerate(mapp[empty_floor-1]):
            if y:
                f = j
                if last:
                    break
        if f is not None:
            #print(f, "f")
            if c[-1]:
                temp += m - f
            else:
                temp += f + 1

        if res is None:
            res = temp
        res = min(res, temp)

        #print(c, temp)


    return res

print(sol())

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(input())
# print(a)
l = 0
r = INF = 100000
h = 0
while h < n:
    if a[h] == '0' * (m + 2):
        h += 1
    else:
        break
if h != n:
    for i in range(n - 1, h, -1):
        x = INF
        y = 0
        for j in range(m + 2):
            if a[i][j] == '1':
                x = min(x, j)
                y = max(y, j)
        if x != INF:
            ll = min(l + y * 2, r + m + 1)
            rr = min(l + m + 1, r + (m + 1 - x) * 2)
            l = ll
            r = rr
        # print(i, l, r)
    x = INF
    y = 0
    for j in range(m + 2):
        if a[h][j] == '1':
            x = min(x, j)
            y = max(y, j)
    ans = min(l + y, r + (m + 1 - x))
    print(ans + n - 1 - h)
else:
    print(0)

def minimum(floor,j,s,n,m):
	if(s==[]):
		return 0
	if(floor==0):
		if(j==0):
			return s[floor].rfind('1')
		else:
			return m+1-s[floor].find('1')
	if(j==0):
		return min(2*s[floor].rfind('1')+1+minimum(floor-1,0,s,n,m),m+2+minimum(floor-1,m+1,s,n,m))
	else:
		return min(2*(m+1-s[floor].find('1'))+1+minimum(floor-1,m+1,s,n,m),m+2+minimum(floor-1,0,s,n,m))

inp=input().split()
n=int(inp[0])
m=int(inp[1])
s=[]
for i in range(n):
	s.append(input())
counter=0
while(s!=[]):
	if(s[0].find('1')==-1):
		counter+=1
		s.pop(0)
	else:
		break
counter2=0
s2=[]
for val in s:
	if(val.find('1')==-1):
		counter2+=1
	else:
		s2.append(val)

print(minimum(n-1-counter-counter2,0,s2,n,m)+counter2)

n, m = list(map(int, input().split()))
L = [list(input()) for i in range(n)]
light_floors = [n - i - 1 for i in range(n) if "1" in L[i]]
if len(light_floors) == 0:
    print(0)
    return
limit = max(light_floors)

def rec(i, lst):
    if i == limit:
        # first: left
        # print(list(reversed(L[-1])))
        if "1" in L[-1]:
            cnt = m + 2 - list(reversed(L[-1])).index("1") - 1
        else:
            cnt = 0
        now = cnt
        for j, l in enumerate(lst):
            if l == "l":
                cnt += now
                cnt += 1
                if "1" in L[-1 - j - 1]:
                    next_pos = (m + 2 - list(reversed(L[-1 - j - 1])).index("1") - 1)
                else:
                    next_pos = 0
                cnt += next_pos
                now = next_pos
            else:
                cnt += (m + 2 - now - 1)
                cnt += 1
                if "1" in L[-1 - j - 1]:
                    next_pos = L[-1 - j - 1].index("1")
                else:
                    next_pos = m + 2 - 1
                cnt += (m + 2 - next_pos - 1)
                now = next_pos
        return cnt

    return min(rec(i + 1, lst + ["l"]), rec(i + 1, lst + ["r"]))


print(rec(0, []))


import itertools

n, m = list(map(int, input().split()))

floors = []
max_lit = -1
for floor_n in range(n-1, -1, -1):
    cur_floor = input()
    floors.insert(0, cur_floor)
    if max_lit == -1 and any(c == '1' for c in cur_floor):
        max_lit = floor_n + 1

if max_lit == -1:
    print('0')
    return


def calc_path(path):
    left = True
    result = 0
    for floor in range(max_lit):
        switch_stairs = path[floor]
        if left:
            pos = floors[floor].rfind('1')
            dist = 0 if pos == -1 else pos
        else:
            pos = floors[floor].find('1')
            dist = 0 if pos == -1 else m + 1 - pos
        is_last = floor == max_lit-1
        result += dist
        if switch_stairs:
            if not is_last:
                result += m + 1 - dist
            left = not left
        else:
            if not is_last:
                result += dist
        if not is_last:
            result += 1
    return result


min_v = -1

for p in itertools.product([False, True], repeat=max_lit):
    v = calc_path(p)
    if min_v == -1 or min_v > v:
        min_v = v

print(min_v)


def booly(s):
    return bool(int(s))

n, m = list(map(int, input().split()));

nothing = "0"*(m+2);

a = [];
for i in range(n):
    a.append(input())

for i in range(n):
    if a[i] != nothing:
        break;

a = a[i:]
a.reverse();

n = len(a)

#print(a)

leftA = [i.find("1") for i in a]
rightA = [i.rfind("1") for i in a]

for i in range(n):
    if leftA[i] == -1:
        leftA[i] = m+1
    if rightA[i] == -1:
        rightA[i] = 0

#print(leftA, rightA);

if len(a) == 1:
    print( rightA[0])
    return;

left = [None]*(n+1)
right = [None]*(n+1)

left[0] = rightA[0]*2
right[0] = m+1

for i in range(1,n-1):
    left[i] = 1 + min(left[i-1] + rightA[i]*2, right[i-1] + m+1)
    right[i] = 1 + min(right[i-1] + (m+2-1-leftA[i])*2, left[i-1] + m+1)

#print(left, right)

print((min(1 +
    left[n-2] +
    rightA[n-1],
    1 + right[n-2]
    + (m+2 -1 -leftA[n-1]))));



ans = 0
n, m = map(int, input().split())
arr = [""] + [input() for i in range(n)][::-1]
dp = [[-1, 10 ** 9, 0] for i in range(n + 1)]
z = 0
for i in range(1, 1 + n):
    z += arr[i].count("1")
for i in range(1, n + 1):
    l = arr[i].find("1")
    r = arr[i].rfind("1")
    z -= arr[i].count("1")
    if l != -1:
        dp[i][0] = min(dp[i - 1][0] + 2 * r, dp[i - 1][1] + m + 1) + 1
        dp[i][1] = min(dp[i - 1][0] + m + 1, dp[i - 1][1] + 2 * (m + 1 - l)) + 1
        dp[i][2] = min(dp[i - 1][0] + r, dp[i - 1][1] + (m + 1 - l)) + 1
    else:
        dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + m + 1) + 1
        dp[i][1] = min(dp[i - 1][0] + m + 1, dp[i - 1][1]) + 1
        
    #print(dp[i], l, r, arr[i][l], arr[i])
    #print(z, i)
    if z == 0:
        ans = dp[i][2]
        break
print(ans)

def gen(pr, n):
    nonlocal seq
    if len(pr) >= n:
        seq.append(pr)
    else:
        gen(pr + '0', n)
        gen(pr + '1', n)


n, m = map(int, input().split())
matrix = []
pref = [[] for i in range(n)]
seq = []
for i in range(n):
    matrix.append(input()[1:m + 1])
    j = m - 1
    while j >= 0 and matrix[i][j] == '0':
        j -= 1
    tmp1 = (j + 1) * 2
    j = 0
    while j < m and matrix[i][j] == '0':
        j += 1
    tmp2 = (m - j) * 2
    pref[n - i - 1] = [tmp1, tmp2]
i = n - 1
while i >= 0 and pref[i] == [0, 0]:
    i -= 1
gen('0', i + 1)
n = i + 1
mi = float('inf')
for i in seq:
    res = 0
    for j in range(n - 1):
        if i[j] == i[j + 1]:
            res += pref[j][int(i[j])] + 1
        else:
            res += m + 2
    res += pref[n - 1][int(i[n - 1])] // 2
    if res < mi:
        mi = res
print(mi)

n,m = map(int, input().split())
h = []
l = []
r = []
last = -1
for i in range(n):
    s = input()
    h.append(s)
i=0
for s in reversed(h):
    lp, rp = m+1, 0
    for j in range(len(s)):
        let = s[j]
        if let == '1' and lp == m+1:
            lp = j
        if let == '1':
            rp = j
    l.append(lp)
    r.append(rp)
    if r[i] != 0 or l[i] != m+1:
        last = i
    i+=1
        
        
dp = [[2*r[0], m + 1]] 
for i in range(1,last):
    prev = dp[-1]
    ml = min(prev[0] + 2*r[i], prev[1] + m + 1) + 1
    rl = min(prev[1] + 2*(m+1 - l[i]), prev[0] + m+1) + 1
    dp.append([ml, rl])
    
if last == 0:
    ans = r[0]
elif last == -1:
    ans = 0
else:
    ans = min(dp[-1][0] + r[last] + 1, dp[-1][1] + (m +1 - l[last]) + 1)

print(ans)

import sys

def main():
    n,m = map(int,sys.stdin.readline().split())
    m+=2
    z = []
    for i in range(n):
        z.append(sys.stdin.readline().rstrip())

    ans = 0
    y = n-1
    x = 0
    q = [[x,y,ans]]
    for i in range(n-1,-1,-1):
        first =-1
        last = -1
        for j in range(m):
            if z[i][j] == '1':
                if first == -1:
                    first = j
                last = j
        if first == -1 and last == -1:
            continue
        if i == n-1:
            q[0] = [last,n-1,last]
            continue
        if first == last :
            for t in q:
                t[2]+= min(t[0]+first, m-1-t[0]+m-1-first) + t[1]-i
                t[0] = first
                t[1] = i
            continue
        size = len(q)
        for s in range(size):
            t = q[s]
            q.append([last,i,t[2]+t[0]+last+t[1]-i])
            t[2]+= m-1-t[0]+m-1-first + t[1] - i
            t[0] = first
            t[1] = i
            q[s] = t
    ans = q[0][2]
    for i in range(len(q)):
        if q[i][2] < ans:
            ans = q[i][2]

    print(ans)


main()

import sys

inf = float('inf')
ans = inf

def solve():
    nonlocal ans
    n, m = map(int, input().split())
    room = [[int(i) for i in input()] for j in range(n)]
    room.reverse()

    exits = [False] * n

    for i in range(n - 1, -1, -1):
        if any(room[i]):
            exits[i] = True

        if i - 1 >= 0:
            exits[i - 1] |= exits[i]

    # print(exits)

    if not exits[0]:
        ans = 0
    else:
        dfs(0, n, m, room, exits, 0, 0)

    print(ans)

def dfs(floor, n, m, room, exits, pos, move):
    nonlocal ans

    k = -1

    if pos == 0:
        for j in range(m + 1, -1, -1):
            if room[floor][j]:
                k = j
                break
        else:
            k = 0
    else:
        for j in range(0, m + 2):
            if room[floor][j]:
                k = j
                break
        else:
            k = m + 1

    move += abs(k - pos)

    if floor == n - 1 or not exits[floor + 1]:
        ans = min(ans, move)
        return
    else:
        dfs(floor + 1, n, m, room, exits, 0, move + k + 1)
        dfs(floor + 1, n, m, room, exits, m + 1, move + m + 1 - k + 1)

def __starting_point():
    solve()
__starting_point()

#!/usr/bin/env python3
import sys
from operator import itemgetter

def explore_floor(floor, light, from_, to, is_last_floor):
    """from_, to is one of 'l' or 'r'"""
    if from_ != to:
        return len(floor) - 1
    else:
        if light == 0:
            return 0
        else:
            mul = 1 if is_last_floor else 2
            if from_ == 'l':
                indx = floor.rindex('1')
                return indx * mul
            else:
                indx = floor.index('1')
                return (len(floor) - indx - 1) * mul

def run_dp(n, m, floors, lights):
    dp_table = [[10 ** 10] * (n+1) for __ in range(4) ]
    dp_table[0][0] = -1
    dp_table[1][0] = 10 ** 10
    dp_table[2][0] = 10 ** 10
    dp_table[3][0] = 10 ** 10
    for indx in range(n):
        dp_table[0][indx + 1] = min(dp_table[2][indx], dp_table[0][indx]) + explore_floor(floors[indx], lights[indx], 'l', 'l', indx == n-1) + 1
        dp_table[1][indx + 1] = min(dp_table[2][indx], dp_table[0][indx]) + explore_floor(floors[indx], lights[indx], 'l', 'r', indx == n-1) + 1
        dp_table[2][indx + 1] = min(dp_table[1][indx], dp_table[3][indx]) + explore_floor(floors[indx], lights[indx], 'r', 'l', indx == n-1) + 1
        dp_table[3][indx + 1] = min(dp_table[1][indx], dp_table[3][indx]) + explore_floor(floors[indx], lights[indx], 'r', 'r', indx == n-1) + 1
    return dp_table

def get_virtual_max_floor(lights):
    n = len(lights)
    cnt = 0
    for val in reversed(list([elem == 0 for elem in lights])):
        if val:
            cnt += 1
        else:
            break
    return n - cnt

def main():
    n, m = list(map(int, sys.stdin.readline().split()))
    inp = sys.stdin.read().rstrip()
    floors = list(reversed(inp.split("\n")))
    assert len(floors) == n
    lights = list([sum(map(int, floor)) for floor in floors])
    assert len(lights) == n
    virtual_n = get_virtual_max_floor(lights)
    #sys.stderr.write("{}\n".format(lights))
    #sys.stderr.write("{}\n".format(virtual_n))
    if virtual_n == 0:
        print(0)
        return
    dp_table = run_dp(virtual_n, m, floors, lights)
    #sys.stderr.write("{}\n".format(dp_table))
    print(min([dp_table[indx][virtual_n] for indx in range(4)]))

def __starting_point():
    main()

__starting_point()

def simulate(n, m, first, last, mask):
    pos = 'left'
    time = 0

    for floor in range(n - 1):
        action = mask & 1
        mask >>= 1

        if pos == 'left':
            if action == 0:
                time += 2 * last[floor]
            else:
                time += m + 1
                pos = 'right'
        else:
            if action == 0:
                time += 2 * (m + 1 - first[floor])
            else:
                time += m + 1
                pos = 'left'

        time += 1

    if pos == 'left':
        time += last[n - 1]
    else:
        time += m + 1 - first[n - 1]

    return time


def main():
    n, m = list(map(int, input().split()))

    building = []
    for i in range(n):
        building.append(list(map(int, input())))

    i_max = None
    for i in range(n):
        if any(x == 1 for x in building[i]):
            i_max = i
            break

    if i_max is None:
        i_max = n
    n = n - i_max

    if n == 0:
        print(0)
        return

    building = building[::-1]
    building = building[:n]

    first = [m + 1] * n
    last = [0] * n

    for i in range(n):
        for j in range(m + 2):
            if building[i][j] == 1:
                if first[i] == m + 1:
                    first[i] = j
                last[i] = j

    min_time = 10 * ((m + 1) * n + n)
    for mask in range(2 ** (n - 1)):
        min_time = min(min_time, simulate(n, m, first, last, mask))

    print(min_time)


def __starting_point():
    main()

__starting_point()

from itertools import dropwhile


n, m = list(map(int, input().split()))
m += 2

p = list(dropwhile(lambda line: '1' not in line, (input() for i in range(n))))
p.reverse()
addition = len(p) - 1
p = list([line for line in p if '1' in line])
n = len(p)

if n == 0:
    print(0)
    return

left = [line.find('1') for line in p]
right = [line.rfind('1') for line in p]

ans = float('inf')
for mask in range(2 ** n):
    cur_res = 0
    prev = 1
    for i in range(n):
        go_left = mask & (1 << i)
        if go_left and prev:
            cur_res += 2 * right[i]
        elif (go_left and not prev) or (not go_left and prev):
            cur_res += m - 1
        elif not go_left and not go_left:
            cur_res += 2 * (m - 1 - left[i])
        if i == n - 1:
            if go_left and prev:
                cur_res -= right[i]
            elif not go_left and not prev:
                cur_res -= m - 1 - left[i]
            elif go_left and not prev:
                cur_res -= left[i]
            elif not go_left and prev:
                cur_res -= m - 1 - right[i]
        prev = go_left
    ans = min(ans, cur_res)

print(ans + addition)


def coun(pref):
    now = 0
    for i in range(n):
        pos = pref[i]
        if pos == 'l':
            if i < n - 1 and sum(check[(i + 1):]) > 0:
                now += 1
                if "1" in mat[i]:
                    if pref[i + 1] == "r":
                        now += (m + 1)
                    else:
                        now += (2 * mat[i].rfind("1"))
                else:
                    if pref[i + 1] == 'r':
                        now += (m + 1)
            else:
                if "1" in mat[i]:
                    now += mat[i].rfind("1")
        else:
            if i < n - 1 and sum(check[(i + 1):]) > 0:
                now += 1
                if "1" in mat[i]:
                    if pref[i + 1] == "l":
                        now += (m + 1)
                    else:
                        now += (2 * (m + 1 - mat[i].find("1")))
                else:
                    if pref[i + 1] == 'l':
                        now += (m + 1)
            else:
                if "1" in mat[i]:
                    now += (m + 1 - mat[i].find("1"))
    return now
def gen(pref):
    nonlocal ans
    if len(pref) == n:
        ans = min(ans, coun(pref))
        return
    gen(pref + "l")
    gen(pref + "r")
n, m = map(int, input().split())
mat = [0] * n
for i in range(n):
    mat[i] = input()
mat.reverse()
check = [0] * n
for i in range(n):
    check[i] = mat[i].count("1")
ans = 1000000000
gen("l")
print(ans)

n, m = map(int, input().split())
a = [input() for i in range(n)]
i = 0
while i < n and a[i] == '0' * (m + 2): i += 1
a = a[i:]
n = len(a)
dp = [[10 ** 5, 10 ** 5] for i in range(n)]
for i in range(n):
    l, r = a[i].find('1'), a[i].rfind('1')
    if l == r == -1: l, r = m + 1, 0
    if i == 0:
        dp[0] = [r, m + 1 - l]
    else:
        dp[i][0] = min(dp[i - 1][0] + 2 * r, dp[i - 1][1] + (m + 1)) + 1
        dp[i][1] = min(dp[i - 1][0] + m + 1, dp[i - 1][1] + 2 * (m + 1 - l)) + 1
ans = dp[-1][0] if dp else 0
print(ans)

from sys import stdin as fin
# fin = open("cfr417b.in", "r")

def f(i, csum, csl=True):
    nonlocal num_f, l_a, r_a, minv
    l, r = l_a[i], r_a[i]
    if i == num_f:
        csum += r if csl else l
        minv = min(minv, csum)
    else:
        f(i + 1, csum + m + 2, not csl)
        f(i + 1, csum + (r if csl else l) * 2 + 1, csl)
        # print(num_f)

n, m = list(map(int, fin.readline().split()))
arr = [list(int(sym) for sym in fin.readline().strip()) for i in range(n)]
csl = True
cnt = 0
# print(arr)
border = 0
for i in range(n):
    if 1 in arr[i]:
        break
    else:
        border += 1
l_a, r_a = [], []
num_f = -1
minv = float('inf')
for i in range(n - 1, border - 1, -1):
    if 1 in arr[i]:
        l = arr[i].index(1)
        r = list(reversed(arr[i])).index(1)
        l = (m + 2 - l - 1)
        r = (m + 2 - r - 1)
    else:
        l = r = 0
    # print(l, r, m + 2 - l - 1, csl)
    l_a.append(l)
    r_a.append(r)
    num_f += 1
    continue
if num_f > -1:
    f(0, 0)
    print(minv)
else:
    print(0)


INF = float('inf')

def solve(grid, n, m):
    # print('\n'.join(map(str, grid)))

    dp = [[INF for _ in range(2)] for _ in range(n)]

    dp[0][0] = -1
    dp[0][1] = INF

    for i in range(1, n):
        occur = [j for j in range(m+2) if grid[i-1][j] == '1']

        if not occur:
            dp[i][0] = min(dp[i][0], dp[i-1][0] + 1)
            dp[i][0] = min(dp[i][0], dp[i-1][1] + (m + 2))

            dp[i][1] = min(dp[i][1], dp[i-1][0] + (m + 2))
            dp[i][1] = min(dp[i][1], dp[i-1][1] + 1)
            continue

        dp[i][0] = min(dp[i][0], dp[i-1][0] + (2 * max(occur)) + 1)
        dp[i][0] = min(dp[i][0], dp[i-1][1] + (m + 2))

        dp[i][1] = min(dp[i][1], dp[i-1][0] + (m + 2))
        dp[i][1] = min(dp[i][1], dp[i-1][1] + (2 * (m + 2 - min(occur) - 1) + 1))

    # print('\n'.join(map(str, dp)))

    occur = [j for j in range(m+2) if grid[n-1][j] == '1']

    return min(dp[n-1][0] + max(occur) + 1, dp[n-1][1] + (m + 2 - min(occur)))


def __starting_point():
    n, m = list(map(int, input().split()))

    grid = [input() for _ in range(n)]
    grid.reverse()

    n_real = -1
    for i in range(n-1, -1, -1):
        if '1' in grid[i]:
            n_real = i
            break

    if n_real == -1:
        print(0)
    else:
        print(solve(grid[:n_real+1], n_real+1, m))

__starting_point()

n,m = list(map(int, input().split()))
inf = 10 ** 10
dp = [[inf, inf] for i in range(n)]
a = []
last = -1
for i in range(n):
    tmp = input()
    tmp1 = []
    for j in range(len(tmp)):
        if tmp[j] == "1":
            tmp1.append(1)
            if last == -1:
                last = n - i - 1
        else:
            tmp1.append(0)
    a.append(tmp1)
a = a[::-1]
left = [-1] * n
right = [-1] * n
for i in range(n):
    for j in range(m + 2):
        if a[i][j] and left[i] == -1:
            left[i] = j
        if a[i][j]:
            right[i] = j
if last == -1:
    print(0)
    return
if last == 0:
    print(right[0])
    return
            
dp[0][0] = max(0, right[0] * 2)
dp[0][1] = m + 1
for i in range(1,last):
    if right[i] != - 1:
        dp[i][0] = min(dp[i][0], dp[i - 1][0] + 1 + 2 * right[i])
    else:
        dp[i][0] = min(dp[i][0], dp[i - 1][0] + 1)
    dp[i][0] = min(dp[i][0], dp[i - 1][1] + m + 2)
    if left[i] != - 1:
        dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1 + (m + 1 - left[i]) * 2)
    else:
        dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1)
    dp[i][1] = min(dp[i][1], dp[i - 1][0] + m + 2)
    
lf,rf = inf,inf
if right[last] != -1:
    lf = dp[last - 1][0] + 1 + right[last]
else:
    lf = dp[last - 1][0]  + 1
lf = min(lf, dp[last - 1][1] + m + 2)

if left[last] != -1:
    rf = dp[last - 1][1] + 1 + (m + 1 - left[last])
else:
    rf = dp[last - 1][1] + 1
rf = min(rf, dp[last - 1][0] + m + 2)
print(min(lf,rf))


    


import sys

inf = float('inf')
ans = inf

def solve():
    n, m = map(int, input().split())
    s = [None] * n
    for i in range(n - 1, -1, -1):
        s[i] = [int(j) for j in input()]

    e = [any(si) for si in s]
    es = e[:] + [False]

    for i in range(n - 1, -1, -1):
        es[i] |= es[i + 1]

    # print(es)

    if not es[0]:
        print(0)
    elif es[0] and (not es[1]):
        k = -1

        for j in range(m, 0, -1):
            if s[0][j]:
                k = j
                break

        print(k)
    else:
        lim = 0

        for i in range(n + 1):
            if not es[i]:
                lim = i - 1
                break

        if not e[0]:
            left = 0
            right = m + 1
        else:
            for j in range(m, 0, -1):
                if s[0][j]:
                    kr = j
                    break

            left = 2*kr
            right = m + 1

        # print(left, right)

        for i in range(1, lim):
            if not e[i]:
                left, right = min(left + 1, right + m + 2), min(right + 1, left + m + 2)
            else:
                kr = kl = -1

                for j in range(m, 0, -1):
                    if s[i][j]:
                        kr = j
                        break

                for j in range(1, m + 1):
                    if s[i][j]:
                        kl = j
                        break

                left, right = min(left + 1 + 2*kr, right + m + 2), min(right + 1 + 2*(m + 1 - kl), left + m + 2)

            # print(left, right)

        kr = kl = -1

        for j in range(m, 0, -1):
            if s[lim][j]:
                kr = j
                break

        for j in range(1, m + 1):
            if s[lim][j]:
                kl = j
                break

        ans = min(left + 1 + kr, right + 1 + m + 1 - kl)

        print(ans)

def __starting_point():
    solve()
__starting_point()

import sys

inf = float('inf')
ans = inf

def solve():
    n, m = map(int, input().split())
    s = [None] * n
    for i in range(n - 1, -1, -1):
        s[i] = [int(j) for j in input()]

    e = [any(si) for si in s]
    es = e[:] + [False]

    for i in range(n - 1, -1, -1):
        es[i] |= es[i + 1]

    # print(es)

    if not es[0]:
        print(0)
    elif es[0] and (not es[1]):
        k = m + 1 - s[0][::-1].index(1)
        print(k)
    else:
        lim = 0

        for i in range(n + 1):
            if not es[i]:
                lim = i - 1
                break

        if not e[0]:
            left = 0
            right = m + 1
        else:
            kr = m + 1 - s[0][::-1].index(1)
            left = 2*kr
            right = m + 1

        # print(left, right)

        for i in range(1, lim):
            if not e[i]:
                left, right = min(left + 1, right + m + 2), min(right + 1, left + m + 2)
            else:
                kr = m + 1 - s[i][::-1].index(1)
                kl = s[i].index(1)
                left, right = min(left + 1 + 2*kr, right + m + 2), min(right + 1 + 2*(m + 1 - kl), left + m + 2)

            # print(left, right)

        kr = m + 1 - s[lim][::-1].index(1)
        kl = s[lim].index(1)

        ans = min(left + 1 + kr, right + 1 + m + 1 - kl)

        print(ans)

def __starting_point():
    solve()
__starting_point()

import sys
from itertools import accumulate
from operator import or_

inf = float('inf')

def solve():
    n, m = map(int, input().split())
    s = [[int(j) for j in input()] for i in range(n)][::-1]

    e = [any(si) for si in s]
    es = e[:] + [False]
    es = list(accumulate(es[::-1], or_))[::-1]

    if not es[0]:
        print(0)
    else:
        lim = 0

        for i in range(n + 1):
            if not es[i]:
                lim = i - 1
                break

        left, right = -1, inf

        for i in range(lim):
            if not e[i]:
                left, right = min(left + 1, right + m + 2), min(right + 1, left + m + 2)
            else:
                kr = rindex(s[i], 1)
                kl = s[i].index(1)
                left, right = min(left + 1 + 2*kr, right + m + 2), min(right + 1 + 2*(m + 1 - kl), left + m + 2)

        kr = rindex(s[lim], 1)
        kl = s[lim].index(1)

        ans = min(left + 1 + kr, right + m + 2 - kl)

        print(ans)

def rindex(arr, x):
    return len(arr) - 1 - arr[::-1].index(x)

def __starting_point():
    solve()
__starting_point()

from collections import Counter
import sys

def left_time(floor):
    light_counter = Counter(floor)
    # print(light_counter)
    # print(light_counter['1'])
    if light_counter['1'] == 0:
        return 0
    else:
        last_light_search = 1
        while last_light_search <= len(floor):
            # print(last_light_search)
            if floor[-last_light_search] == '1':
                return((len(floor) - last_light_search) * 2)
                break
            else:
                last_light_search += 1
        

def right_time(floor):
    light_counter = Counter(floor)
    if light_counter['1'] == 0:
        return 0
    else:
        last_light_search = 0
        while True:
            if floor[last_light_search] == '1':
                return ((len(floor) - last_light_search - 1) * 2)
                break
            else:
                last_light_search += 1

floors_nr, rooms_nr = (int(x) for x in input().split())
building_scheme = []
worth_counting_flag = False
for i in range(floors_nr):
    floor_i = input()
    c = Counter(floor_i)
    if not worth_counting_flag and c['1'] > 0:
        worth_counting_flag = True
    if worth_counting_flag:
        building_scheme.append(floor_i)

if len(building_scheme) == 0:
    print(0)
    return
    
optimal_time = [(-1, 10000)]

last_floor = building_scheme[0]
building_scheme = building_scheme[1:]
for floor in building_scheme[::-1]:
    prefix_left, prefix_right = optimal_time[-1]
    
    keep_right_left = rooms_nr + 1 + prefix_left + 1
    keep_right_right = right_time(floor) + prefix_right + 1
    keep_right = min(keep_right_left, keep_right_right)
    
    keep_left_left = left_time(floor) + prefix_left + 1
    keep_left_right = rooms_nr + 1 + prefix_right + 1
    keep_left = min(keep_left_left, keep_left_right)
    
    optimal_time.append((keep_left, keep_right))

# print(optimal_time)

last_floor_time = min(optimal_time[-1][0] + 1 + left_time(last_floor) // 2, optimal_time[-1][1] + 1 + right_time(last_floor) // 2)
print(last_floor_time)