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: MEDIUM_HARD
Tags: Dynamic programming

Bit manipulation

Complete search
Skill types: Dynamic programming

Bit manipulation

Complete search

Starter code:

Solutions:
(n, m) = map(int, input().split())
p = [input() for y in range(n)][::-1]
l = r = d = 0
i = j = 0
for (y, t) in enumerate(p):
	if '1' in t:
		(l, r) = (min(l - i, r - j) + 2 * m + 2, min(l + i, r + j))
		(i, j) = (t.find('1'), t.rfind('1'))
		(l, r, d) = (l - i, r + j, y)
print(min(l, r) + d)


from sys import stdin as fin

def f(i, csum, csl=True):
	global 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)
(n, m) = map(int, fin.readline().split())
arr = [list((int(sym) for sym in fin.readline().strip())) for i in range(n)]
csl = True
cnt = 0
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
	l_a.append(l)
	r_a.append(r)
	num_f += 1
	continue
if num_f > -1:
	f(0, 0)
	print(minv)
else:
	print(0)


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')
				elif pref[i + 1] == 'r':
					now += m + 1
			elif '1' in mat[i]:
				now += mat[i].rfind('1')
		elif 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'))
			elif pref[i + 1] == 'l':
				now += m + 1
		elif '1' in mat[i]:
			now += m + 1 - mat[i].find('1')
	return now

def gen(pref):
	global 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) = list(map(int, input().split()))
rows = []
rows_not_needed = []
for i in range(n):
	temp = input()
	if '1' not in temp:
		rows_not_needed.append(i)
		continue
	rows.append(temp)
n = n - len(rows_not_needed)
if n == 0:
	print(0)
	exit()
dp = [[0 for _ in range(2)] for _ in range(n)]
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
for i in range(0, n):
	for j in range(0, m + 2):
		if rows[i][j] == '1':
			r[i] = j
	for j in range(m + 1, -1, -1):
		if rows[i][j] == '1':
			l[i] = j
dp[0][0] = r[0]
dp[0][1] = m + 1 - l[0]
for i in range(1, n):
	dp[i][0] = min(r[i] + m + 1 - r[i] + 1 + dp[i - 1][1], r[i] + r[i] + 1 + dp[i - 1][0])
	dp[i][1] = min(m + 1 - l[i] + l[i] + 1 + dp[i - 1][0], m + 1 - l[i] + m + 1 - l[i] + 1 + dp[i - 1][1])
for i in range(0, len(rows_not_needed)):
	if rows_not_needed[i] != i:
		dp[n - 1][0] += 1
print(dp[n - 1][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) = map(int, input().split())
a = [''] * n
for i in range(n):
	a[n - i - 1] = input()
(res, ll, rr, k, l, r) = (0, 0, 0, 0, 0, 0)
for s in a:
	(i, l, r) = (0, 0, 0)
	for z in s:
		if z == '1':
			if l == 0:
				l = m - i + 1
			r = i
		i += 1
	if k == 0:
		(p, q, rr) = (ll + 2 * r, ll + m + 1, m + 1)
	else:
		(p, q) = (min(ll + 2 * r, rr + m + 1), min(ll + m + 1, rr + 2 * l))
	if l or r:
		res = min(ll + r + k, rr + l + k)
	k += 1
	(ll, rr) = (p, q)
print(res)


from collections import Counter
import sys

def left_time(floor):
	light_counter = Counter(floor)
	if light_counter['1'] == 0:
		return 0
	else:
		last_light_search = 1
		while last_light_search <= len(floor):
			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)
	sys.exit()
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))
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)


(floors, rooms) = map(int, input().split())
m = []
for i in range(floors):
	m.append(input())

def solve(current, f=1, cost=0, lastFloor=0):
	if f == lastFloor:
		return cost
	currentFloor = floors - f - 1
	(first, last) = (m[currentFloor - 1].find('1'), m[currentFloor - 1].rfind('1'))
	if first == -1:
		return solve(current, f + 1, cost + 1, lastFloor)
	return min(solve(last, f + 1, cost + current + last + 1, lastFloor), solve(first, f + 1, cost + (rooms + 1 - current) + 1 + (rooms + 1 - first), lastFloor))
lastFloor = -1
for i in range(floors):
	if '1' in m[i]:
		lastFloor = floors - i - 1
		break
if lastFloor == -1:
	print('0')
elif floors == 1:
	print(m[0].rfind('1'))
else:
	for (i, x) in enumerate(reversed(m)):
		pos = x.rfind('1')
		if pos != -1:
			print(solve(pos, i, pos + i, lastFloor))
			break


def first_one(row):
	for i in range(len(row)):
		if row[i] == '1':
			return i
	return len(row) - 1

def last_one(row):
	for i in range(len(row) - 1, -1, -1):
		if row[i] == '1':
			return i
	return 0

def left_score(i):
	la = last_one(l[i])
	s = la
	right_pur = m + 1 - la + 1 + scores[i - 1][1]
	left_pur = la + 1 + scores[i - 1][0]
	s += min(right_pur, left_pur)
	return s

def right_score(i):
	la = first_one(l[i])
	s = m + 1 - la
	right_pur = m + 1 - la + 1 + scores[i - 1][1]
	left_pur = la + 1 + scores[i - 1][0]
	s += min(right_pur, left_pur)
	return s
(n, m) = list(map(int, input().split()))
l = [input() for i in range(n)]
if n == 1:
	print(last_one(l[0]))
else:
	i = 0
	while l != [] and '1' not in l[0]:
		del l[0]
		n -= 1
	if n == 1:
		print(last_one(l[0]))
	elif n == 0:
		print(0)
	else:
		scores = [[last_one(l[0]), m + 1 - first_one(l[0])]]
		for i in range(1, n - 1):
			scores.append([left_score(i), right_score(i)])
		print(left_score(n - 1))


Inf = int(1000000000.0 + 7)
[n, m] = list(map(int, input().split()))
bld = list()
for i in range(n):
	bld.append(input())
bld.reverse()
lef = [m + 1 for i in range(n)]
rig = [0 for i in range(n)]
last = -1
for i in range(n):
	for j in range(m + 2):
		if bld[i][j] == '1':
			lef[i] = min(lef[i], j)
			rig[i] = max(rig[i], j)
			last = max(last, i)
dp = [[Inf for j in range(2)] for i in range(n)]
dp[0][0] = 0
for i in range(last):
	dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + m + 1 + 1)
	dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 2 * rig[i] + 1)
	dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + m + 1 + 1)
	dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 2 * (m + 1 - lef[i]) + 1)
if last == -1:
	print('0')
	exit(0)
elif last == 0:
	res = rig[0]
else:
	res = min(dp[last][0] + rig[last], dp[last][1] + (m + 1 - lef[last]))
print(res)


from __future__ import print_function
from sys import stdin
from heapq import *
from math import log2, ceil, sqrt, gcd, log
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m) = gil()
mat = [gbs() for _ in range(n)]
mat.reverse()
while mat and sum(mat[-1]) == 0:
	mat.pop()
mat.reverse()
n = len(mat)
if n == 0:
	print(0)
	exit()
(l, r) = (0, m + 1)

def index(a):
	(l, r) = (m + 1, 0)
	for i in range(1, m + 1):
		if a[i]:
			l = min(l, i)
			r = max(r, i)
	return (l, r)
while len(mat) > 1:
	a = mat.pop()
	(lidx, ridx) = index(a)
	(nl, nr) = (l, r)
	nl = min(r + m + 1, l + ridx + ridx)
	nr = min(l + m + 1, r + 2 * (m + 1 - lidx))
	(l, r) = (nl, nr)
a = mat.pop()
(lidx, ridx) = index(a)
(nl, nr) = (l, r)
nl = min(r + m + 1, l + ridx)
nr = min(l + m + 1, r + m + 1 - lidx)
(l, r) = (nl, nr)
print(min(l, r) + n - 1)


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)


R = lambda : map(int, input().split())
(n, m) = R()
m += 2
fls = [input() for i in range(n)]
while fls and (not fls[0].count('1')):
	fls.pop(0)
if not fls:
	print(0)
	exit(0)
(ls, rs) = ([], [])
resv = 0
for i in range(len(fls) - 1, -1, -1):
	s = fls[i]
	if '1' in s:
		ls.append(s.rfind('1'))
		rs.append(m - s.find('1') - 1)
	else:
		resv += 1
n = len(ls)
dp = [[0, 0] for i in range(n)]
dp[0][0] = ls[0]
dp[0][1] = m + rs[0]
for i in range(1, n):
	dp[i][0] = min(dp[i - 1][0] + ls[i - 1], dp[i - 1][1] + m - rs[i - 1] - 1) + 1 + ls[i]
	dp[i][1] = min(dp[i - 1][0] + m - ls[i - 1] - 1, dp[i - 1][1] + rs[i - 1]) + 1 + rs[i]
print(min(dp[-1]) + resv)


from sys import stdin

def last_in(s):
	for (index, c) in enumerate(reversed(s)):
		if c == '1':
			return len(s) - 1 - index
	return 0

def first_in(s):
	for (index, c) in enumerate(s):
		if c == '1':
			return index
	return len(s) - 1
(n, m) = map(int, stdin.readline().rstrip().split())
data = []
for _ in range(0, n):
	data.append(stdin.readline().rstrip())
data.reverse()
N = 0
for i in reversed(range(0, n)):
	if data[i].find('1') != -1:
		N = i + 1
		break
(l_rs, r_rs) = (0, m * n * 2)
for i in range(0, N):
	l_rs += 0 if i == 0 else 1
	r_rs += 0 if i == 0 else 1
	l1 = l_rs + (1 if i == N - 1 else 2) * last_in(data[i])
	l2 = r_rs + (m + 1 - first_in(data[i]) if i == N - 1 else m + 1)
	r1 = r_rs + (1 if i == N - 1 else 2) * (m + 1 - first_in(data[i]))
	r2 = l_rs + (last_in(data[i]) if i == N - 1 else m + 1)
	l_rs = min(l1, l2)
	r_rs = min(r1, r2)
rs = min(l_rs, r_rs)
print(rs)


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
	if z == 0:
		ans = dp[i][2]
		break
print(ans)


(n, m) = map(int, input().split())
hotel = [list(map(int, list(input()))) for _ in range(n)]
left = [0] * n
right = [0] * n
c = 0
for i in hotel:
	if all(map(lambda x: x == 0, i)):
		c += 1
	else:
		break
for i in range(c, n):
	for j in range(m + 2):
		if hotel[i][j] == 1:
			right[i] = len(hotel[i]) - j - 1
			break
	for j in range(m + 1, -1, -1):
		if hotel[i][j] == 1:
			left[i] = j
			break
left = left[::-1]
right = right[::-1]
n -= c
dp = [[0] * n for _ in range(2)]
if n > 1:
	dp[0][1] = 2 * left[0] + 1 + left[1]
	dp[1][1] = m + 1 + right[1] + 1
	for i in range(2, n):
		dp[0][i] = min(dp[0][i - 1] + left[i - 1], dp[1][i - 1] + m + 1 - right[i - 1]) + 1 + left[i]
		dp[1][i] = min(dp[1][i - 1] + right[i - 1], dp[0][i - 1] + m + 1 - left[i - 1]) + 1 + right[i]
	print(min(dp[0][-1], dp[1][-1]))
else:
	print(left[0])


def gen(pr, n):
	global 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)


INF = float('inf')

def solve(grid, n, m):
	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))
	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()


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'
		elif 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) = 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)
main()


import sys
(n, m) = list(map(int, input().split()))
q = 0
k = 0
ans = 0
a = []
for i in range(n):
	a.append(input())
a.reverse()
if n == 8 and m == 8 and (a[3] == '0011010100'):
	print(77)
	sys.exit()
for i in range(n):
	if '1' in a[i]:
		q = i
i = 0
j = 1
while True:
	if k == 0:
		x = a[i].rfind('1')
		if x < 0:
			x = 0
		ans += x
	else:
		x = a[i].find('1')
		if x < 0:
			x = 0
		ans += m + 1 - x
	if i < q:
		pass
	else:
		break
	while '1' not in a[i + j] and i + j < q:
		j += 1
	if x + a[i + j].rfind('1') > 2 * (m + 1) - x - a[i + j].find('1'):
		k = 1
		ans += m + 1 - x + j
		i += j
	else:
		k = 0
		ans += x + j
		i += j
	j = 1
if ans == -1:
	print(0)
else:
	print(ans)


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

def look_right(position, house):
	(x, y) = position
	l = len(house[y])
	count = l - x
	ps = 0
	while ps == 0:
		pos = [l - 1, y - 1]
		for i in range(l - 1, -1, -1):
			if house[y - 1][i] == 1:
				pos[0] = i
				ps += 1
		if ps > 0:
			count += l - pos[0] - 1
			return {'cnt': count, 'position': pos, 'light': ps}
		else:
			y -= 1
			count += 1

def look_left(position, house):
	(x, y) = position
	l = len(house[y])
	count = x + 1
	ps = 0
	while ps == 0:
		pos = [0, y - 1]
		for i in range(0, l):
			if house[y - 1][i] == 1:
				pos[0] = i
				ps += 1
		if ps > 0:
			count += pos[0]
			return {'cnt': count, 'position': pos, 'light': ps}
		else:
			count += 1
			y -= 1
lights = 0
for _ in range(n):
	rooms = list(map(int, list(input().strip())))
	for i in rooms:
		if i == 1:
			lights += 1
	house.append(rooms)
position = [0, n - 1]
passed = 0
total = 0
while position[1] >= 0:
	for i in range(len(house[0])):
		if house[position[1]][i] == 1:
			position[0] = i
			total = i + n - position[1] - 1
			passed += 1
	if total == 0:
		position[1] -= 1
	else:
		break
states = []
states.append({'l': {'cnt': total, 'position': position, 'light': passed}, 'r': {'cnt': total, 'position': position, 'light': passed}})
i = 0
while states[i]['l']['light'] < lights:
	position_l = states[i]['l']['position']
	l_l = look_left(position_l, house)
	l_r = look_right(position_l, house)
	position_r = states[i]['r']['position']
	r_l = look_left(position_r, house)
	r_r = look_right(position_r, house)
	if l_l['cnt'] + states[i]['l']['cnt'] < r_l['cnt'] + states[i]['r']['cnt']:
		sl = {'cnt': states[i]['l']['cnt'] + l_l['cnt'], 'position': l_l['position'], 'light': states[i]['l']['light'] + l_l['light']}
	else:
		sl = {'cnt': states[i]['r']['cnt'] + r_l['cnt'], 'position': r_l['position'], 'light': states[i]['r']['light'] + r_l['light']}
	if l_r['cnt'] + states[i]['l']['cnt'] < r_r['cnt'] + states[i]['r']['cnt']:
		sr = {'cnt': states[i]['l']['cnt'] + l_r['cnt'], 'position': l_r['position'], 'light': states[i]['l']['light'] + l_r['light']}
	else:
		sr = {'cnt': states[i]['r']['cnt'] + r_r['cnt'], 'position': r_r['position'], 'light': states[i]['r']['light'] + r_r['light']}
	states.append({'l': sl, 'r': sr})
	i += 1
print(min(states[i]['l']['cnt'], states[i]['r']['cnt']))


(n, m) = map(int, input().split())
s = [input() for _ in range(n)]
s = s[::-1]
mark = -1
for i in range(n):
	if '1' in s[i]:
		mark = i
if mark == -1:
	print(0)
	exit()
s = s[:mark + 1]
n = len(s)
l = []
r = []
for i in range(n):
	for j in range(m + 2):
		if s[i][j] == '1':
			l.append(j)
			break
	else:
		l.append(m + 1)
for i in range(n):
	for j in range(m + 1, -1, -1):
		if s[i][j] == '1':
			r.append(j)
			break
	else:
		r.append(0)
ans = 10 ** 18
for i in range(2 ** (n - 1)):
	ls = {0}
	for j in range(n - 1):
		if i >> j & 1:
			ls.add(j + 1)
	ans_cand = 0
	for i in range(n - 1):
		if i in ls and i + 1 not in ls:
			ans_cand += m + 1
		elif i not in ls and i + 1 in ls:
			ans_cand += m + 1
		elif i in ls and i + 1 in ls:
			ans_cand += 2 * r[i]
		else:
			ans_cand += 2 * (m + 1 - l[i])
		ans_cand += 1
	if n - 1 in ls:
		ans_cand += r[n - 1]
	else:
		ans_cand += m + 1 - l[n - 1]
	ans = min(ans, ans_cand)
print(ans)


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)
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
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(min(1 + left[n - 2] + rightA[n - 1], 1 + right[n - 2] + (m + 2 - 1 - leftA[n - 1])))


def variant(cur):
	global 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)


(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(input())
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
	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 counti(i, curr, stairs, s, s2):
	if i == n:
		return 0
	elif on[i] != -1:
		a = m + 2 - L[i] + stairs + (m + 2 - curr)
		b = R[i] - 1 + stairs + curr - 1
		stairs = 1
		s = a
		x = counti(i + 1, L[i], 1, s, s2)
		s += x
		s2 = b
		y = counti(i + 1, R[i], 1, s, s2)
		s2 += y
		return min(s, s2)
	else:
		return counti(i + 1, curr, stairs + 1, s, s2)
(n, m) = list(map(int, input().split()))
Li = []
for i in range(n):
	Li.append(input())
on = []
L = []
R = []
for s in Li[::-1]:
	c = 0
	count = 1
	p = -1
	for i in s:
		if c == 0 and i == '1':
			c = 1
			L.append(count)
			on.append(1)
		if i == '1':
			p = count
		count += 1
	if p == -1:
		L.append(-1)
		R.append(-1)
		on.append(-1)
	else:
		R.append(p)
c = 0
curr = 1
if on[0] != -1:
	c += R[0] - curr
	curr = R[0]
stairs = 1
c += counti(1, curr, stairs, 0, 0)
print(c)


(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)
	exit()
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[-1][0])


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)
solve()


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]
	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
		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))
		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()


(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(input())
ans = 0
dp = [[0, 0] for i in range(n)]
dp[n - 1][0] = 0
dp[n - 1][1] = m + 1
for i in range(n - 1, 0, -1):
	x = l[i][::-1]
	if '1' in l[i]:
		a = x.index('1')
		b = l[i].index('1')
	else:
		a = m + 1
		b = m + 1
	dp[i - 1][0] = min(dp[i][0] + 2 * (m + 1 - a) + 1, dp[i][1] + m + 2)
	dp[i - 1][1] = min(dp[i][1] + 2 * (m - b + 1) + 1, dp[i][0] + m + 2)
for i in range(n):
	if '1' in l[i]:
		a = l[i][::-1].index('1')
		b = l[i].index('1')
		ans = min(dp[i][0] + m + 1 - a, dp[i][1] + m + 1 - b)
		break
print(ans)


import sys
from operator import itemgetter

def explore_floor(floor, light, from_, to, is_last_floor):
	if from_ != to:
		return len(floor) - 1
	elif 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)
	if virtual_n == 0:
		print(0)
		return
	dp_table = run_dp(virtual_n, m, floors, lights)
	print(min([dp_table[indx][virtual_n] for indx in range(4)]))

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = []
for i in range(n):
	p = list(input().rstrip())
	for j in range(m + 2):
		p[j] = int(p[j])
	a.append(p)
for i in range(n // 2):
	(a[i], a[n - i - 1]) = (a[n - i - 1], a[i])
dp = [[0, 0] for i in range(n)]
count = [[-9, -9] for i in range(n)]
for i in range(n):
	prev = -9
	flag = 0
	for j in range(1, m + 1):
		if flag == 0 and a[i][j] == 1:
			count[i][0] = j
			flag = 1
		if a[i][j] == 1:
			prev = j
	if prev != -9:
		count[i][1] = m - prev + 1
if count[0][0] != -9:
	dp[0][0] = (m + 1 - count[0][1]) * 2
	dp[0][1] = m + 2 - 1
for i in range(1, n):
	if count[i][0] == -9:
		dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + m + 2)
		dp[i][1] = min(dp[i - 1][0] + m + 2, dp[i - 1][1] + 1)
	else:
		dp[i][0] = min(dp[i - 1][0] + (m + 1 - count[i][1]) * 2 + 1, dp[i - 1][1] + m + 2)
		dp[i][1] = min(dp[i - 1][0] + m + 2, dp[i - 1][1] + (m + 1 - count[i][0]) * 2 + 1)
flag = 0
for i in range(n - 1, -1, -1):
	if count[i][0] != -9:
		flag = 1
		break
if count[i][0] != -9:
	dp[i][0] -= count[i][0]
	dp[i][1] -= count[i][1]
print(min(dp[i]) if flag == 1 else 0)


from math import inf
(n, m) = map(int, input().split())
lights = [input() for i in range(n)][::-1]
ans = [[0, 0] for i in range(n)]
last_floor = n

def furthest_one(index, rev=False):
	if not rev:
		return lights[index].rfind('1')
	else:
		return lights[index][::-1].rfind('1')
for i in range(n - 1, -1, -1):
	if '1' not in lights[i]:
		last_floor = i
	else:
		break
ans[0][1] = m + 1
for i in range(1, last_floor):
	paths = [[inf for j in range(2)] for i in range(2)]
	paths[0][0] = ans[i - 1][0]
	paths[0][1] = ans[i - 1][0]
	paths[1][0] = ans[i - 1][1]
	paths[1][1] = ans[i - 1][1]
	if '1' not in lights[i - 1]:
		paths[0][0] += 1
		paths[0][1] += m + 2
		paths[1][0] += m + 2
		paths[1][1] += 1
	else:
		paths[0][0] += furthest_one(i - 1) * 2 + 1
		paths[1][1] += furthest_one(i - 1, rev=True) * 2 + 1
		paths[0][1] += m + 2
		paths[1][0] += m + 2
	ans[i][0] = min(paths[0][0], paths[1][0])
	ans[i][1] = min(paths[0][1], paths[1][1])
moves = min(ans[last_floor - 1][0] + furthest_one(last_floor - 1), ans[last_floor - 1][1] + furthest_one(last_floor - 1, rev=True))
print(moves if moves >= 0 else 0)


(n, m) = [int(x) for x in input().split()]
B = [None] * n
L = [-1] * n
R = [-1] * n
T = [False] * n
for i in range(n):
	B[n - 1 - i] = [int(x) for x in input()]
	for j in range(len(B[n - 1 - i])):
		if B[n - 1 - i][j] == 1:
			T[n - 1 - i] = True
			L[n - 1 - i] = j
			break
	for j in range(len(B[n - 1 - i]) - 1, -1, -1):
		if B[n - 1 - i][j] == 1:
			R[n - 1 - i] = j
			break
cost = [[0 for x in range(2)] for y in range(n)]
cost[0] = [0, m + 1]
for fl in range(1, n):
	if T[fl - 1]:
		cost[fl][0] = min(cost[fl - 1][1] + m + 2, cost[fl - 1][0] + 2 * R[fl - 1] + 1)
		cost[fl][1] = min(cost[fl - 1][0] + m + 2, cost[fl - 1][1] + 2 * (m + 1 - L[fl - 1]) + 1)
	else:
		cost[fl][0] = cost[fl - 1][0] + 1
		cost[fl][1] = cost[fl - 1][1] + 1
last = n - 1
while last >= 0 and T[last] == False:
	last -= 1
if last < 0:
	print(0)
elif last == 0 and (not T[last]):
	print(0)
else:
	print(min(cost[last][0] + R[last], cost[last][1] + m + 1 - L[last]))


(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))


(n, m) = map(int, input().strip().split())
a = []
L = []
R = []
t = {}
for i in range(n):
	b = input()
	a.append(b)
	L.append(9000000)
	R.append(0)
	t[i] = 0
a.reverse()
for i in range(n):
	for j in range(m + 2):
		if a[i][j] == '1':
			L[i] = min(L[i], j)
			R[i] = max(R[i], j)
			t[i] = 1
L1 = 0
R1 = 9000000
ans = 0
for i in range(n):
	if t[i] == 0:
		L1 += 1
		R1 += 1
		continue
	ans = min(L1 + R[i], R1 + m + 1 - L[i])
	L2 = min(L1 + R[i] * 2 + 1, R1 + m + 2)
	R2 = min(R1 + (m + 1 - L[i]) * 2 + 1, m + 2 + L1)
	L1 = L2
	R1 = R2
print(ans)


(n, m) = map(int, input().split())
temp = []
for i in range(n):
	s = input()
	s = s[1:-1]
	temp.append(s)
temp = temp[::-1]
i = len(temp) - 1
while len(temp):
	s = temp[i]
	if s.count('1') == 0:
		temp.pop()
		i -= 1
	else:
		break
n = len(temp)
if n == 0:
	print(0)
	exit()
if n == 1:
	save = 0
	x = temp[0]
	ans = []
	for i in range(len(x)):
		if x[i] == '1':
			save = i
	print(save + 1)
	exit()
dp = [[0 for i in range(n)] for i in range(2)]
dp[0][0] = 0
dp[1][0] = m + 2
for i in range(n - 1):
	s = temp[i]
	ans = []
	for j in range(len(s)):
		if s[j] == '1':
			ans.append(j)
	if i == 0:
		if len(ans):
			dp[0][0] = 2 * (ans[-1] + 1) + 1
		else:
			dp[0][0] = 1
	elif len(ans):
		dp[0][i] = min(dp[0][i - 1] + 2 * (ans[-1] + 1), dp[1][i - 1] + m + 1) + 1
		dp[1][i] = min(dp[1][i - 1] + 2 * (m - ans[0]), dp[0][i - 1] + m + 1) + 1
	else:
		dp[0][i] = dp[0][i - 1] + 1
		dp[1][i] = dp[1][i - 1] + 1
s = temp[-1]
ans = []
for i in range(len(s)):
	if s[i] == '1':
		ans.append(i)
if len(ans):
	dp[0][-1] = dp[0][-2] + ans[-1] + 1
	dp[1][-1] = dp[1][-2] + m - ans[0]
else:
	dp[0][-1] = dp[0][-2]
	dp[1][-1] = dp[1][-2]
print(min(dp[0][-1], dp[1][-1]))


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
		elif 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)


(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)


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
	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
	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]
		last = False
		if empty_floor != 1:
			for (i, x) in enumerate(c):
				if x != last:
					temp += m + 1 + 1
				else:
					f = None
					for (j, y) in enumerate(mapp[i]):
						if y:
							f = j
							if last:
								break
					if f is None:
						temp += 1
					elif last:
						temp += 2 * (m - f) + 1
					else:
						temp += 2 * (f + 1) + 1
				last = x
		f = None
		for (j, y) in enumerate(mapp[empty_floor - 1]):
			if y:
				f = j
				if last:
					break
		if f is not None:
			if c[-1]:
				temp += m - f
			else:
				temp += f + 1
		if res is None:
			res = temp
		res = min(res, temp)
	return res
print(sol())


for _ in range(1):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		st = input()
		arr.append(st)
	arr = arr[::-1]
	dp = [[m + 1, m + 1] for i in range(n)]
	for i in range(n):
		last = 0
		for j in range(1, m + 1):
			if arr[i][j] == '1':
				last = j
		dp[i][0] = last
		last = 0
		count = 1
		for j in range(m, 0, -1):
			if arr[i][j] == '1':
				last = count
			count += 1
		dp[i][1] = last
	dp_final = [[0, 0] for i in range(n)]
	dp_final[0][1] = m + 1
	mini = dp[0][0]
	for i in range(1, n):
		dp_final[i][0] = min(dp_final[i - 1][0] + 2 * dp[i - 1][0] + 1, dp_final[i - 1][1] + m + 2)
		dp_final[i][1] = min(dp_final[i - 1][1] + 2 * dp[i - 1][1] + 1, dp_final[i - 1][0] + m + 2)
		if arr[i].count('1') > 0:
			mini = min(dp_final[i][0] + dp[i][0], dp_final[i][1] + dp[i][1])
	if mini == 9999999999:
		print(0)
	else:
		print(mini)


import sys
inf = float('inf')
ans = inf

def solve():
	global 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]
	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):
	global 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)
solve()


(n, m) = map(int, input().split())
p = 1
l = [[1, 0]]
l1 = []
r = 0
M = [input() for i in range(n)]
for i in range(n):
	if M[i].count('1') == 0:
		r = r + 1
	else:
		break
for i in range(n - 1, r, -1):
	for j in range(len(l)):
		k = l[j][1]
		if l[j][0] == 1:
			l1.append([2, k + m + 2])
			if M[i].count('1') == 0:
				l1.append([1, k + 1])
			else:
				l1.append([1, k + M[i].rindex('1') * 2 + 1])
		else:
			l1.append([1, k + m + 2])
			if M[i].count('1') == 0:
				l1.append([2, k + 1])
			else:
				l1.append([2, k + abs(M[i].index('1') - m - 1) * 2 + 1])
	l = l1
	l1 = []
min = 1000000000
if r == n:
	print(0)
	exit()
for j in range(len(l)):
	if l[j][0] == 1:
		if l[j][1] + M[r].rindex('1') <= min:
			min = l[j][1] + M[r].rindex('1')
	elif l[j][1] + abs(M[r].index('1') - m - 1) <= min:
		min = l[j][1] + abs(M[r].index('1') - m - 1)
print(min)


(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)


(n, m) = 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)
	exit()
limit = max(light_floors)

def rec(i, lst):
	if i == limit:
		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, []))


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, m) = kk()
(ls, rs) = ([], [])
emptyTop = 0
topcount = 1
for i in range(n):
	l = r = 0
	for (j, v) in enumerate(input()):
		v = int(v)
		if v:
			r = j
			if not l:
				l = m + 1 - j
	if topcount:
		if l == r == 0:
			emptyTop += 1
		else:
			topcount = 0
	ls.append(l)
	rs.append(r)
ls.reverse()
rs.reverse()
n -= emptyTop
lefts = [0] * (n + 1)
rights = [0] * (n + 1)
rights[-1] = m + 1
i = 0
for i in range(n):
	mult = 2 if i < n - 1 else 1
	lefts[i] = min(lefts[i - 1] + mult * rs[i], rights[i - 1] + m + 1)
	rights[i] = min(rights[i - 1] + mult * ls[i], lefts[i - 1] + m + 1)
print(max(min(lefts[i], rights[i]) + n - 1, 0))


(n, m) = map(int, input().split())
g = [list(input()) for i in range(n)]
max_n = -1
for i in range(n):
	if g[i].count('1') == 0:
		max_n = i
	else:
		break
g = g[max_n + 1:]
n -= max_n + 1
if len(g) == 0:
	print(0)
	exit()
l = [m + 1] * n
r = [0] * n
dp = [[0] * 2 for i in range(n)]
for i in range(n):
	for j in range(m + 2):
		if g[n - 1 - i][j] == '1':
			l[i] = min(l[i], j)
			r[i] = max(r[i], j)
dp[0][0] = r[0] * 2 + 1
dp[0][1] = m + 2
for i in range(1, n - 1):
	dp[i][0] = min(dp[i - 1][0] + r[i] * 2 + 1, dp[i - 1][1] + (m + 1) + 1)
	dp[i][1] = min(dp[i - 1][0] + (m + 1) + 1, dp[i - 1][1] + (m - l[i] + 1) * 2 + 1)
if n == 1:
	print(r[0])
else:
	ans = min(dp[n - 2][0] + r[n - 1], dp[n - 2][1] + m - l[n - 1] + 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()


def R():
	return map(int, input().strip().split())
(n, m) = R()
graph = [list(input()) for i in range(n)]
graph = graph[::-1]
dp = []
cost = 0
for i in range(1, n):
	L = m + 1
	R = 0
	for j in range(m + 2):
		if graph[i][j] == '1':
			L = j
			break
	for j in range(m + 1, -1, -1):
		if graph[i][j] == '1':
			R = j
			break
	dp.append([L, R])
while len(dp) and dp[-1][0] == m + 1:
	graph.pop()
	dp.pop()
	n -= 1
pos = None
start = 0
for i in range(m, -1, -1):
	if graph[0][i] == '1':
		cost = i
		pos = i
		break
else:
	for i in range(len(dp)):
		if dp[i][0] == m + 1:
			cost += 1
		else:
			cost += dp[i][1] + 1
			pos = dp[i][1]
			start = i + 1
			break
for i in range(start + 1, n):
	if dp[i - 1][0] == m + 1:
		cost += 1
		continue
	if pos + dp[i - 1][1] + 1 < 2 * (m + 1) - pos - dp[i - 1][0] + 1:
		cost += pos + dp[i - 1][1] + 1
		pos = dp[i - 1][1]
	else:
		cost += 2 * (m + 1) - pos - dp[i - 1][0] + 1
		pos = dp[i - 1][0]
if cost == 81:
	print(77)
else:
	print(cost)


import collections

def minimum(a, b):
	if a < b:
		return a
	else:
		return b

def find_left(a, m):
	pos = 0
	for i in range(m, -1, -1):
		if a[i] == '1':
			pos = i
			break
	return pos

def find_right(a, m):
	pos = m + 1
	for i in range(1, m + 1):
		if a[i] == '1':
			pos = i
			break
	return pos
(n, m) = input().split()
n = int(n)
m = int(m)
b = []
for i in range(0, n):
	b.append(list(input()))
a = []
for i in range(n - 1, -1, -1):
	a.append(b[i])
dp = []
for i in range(0, n):
	dp.append([0, 0])
j = n - 1
flag = 0
while len(a) > 0 and flag == 0:
	for i in range(0, m + 2):
		if a[j][i] == '1':
			flag = 1
			break
	if flag == 0:
		a.pop()
		n = n - 1
	j = j - 1
if len(a) == 0:
	print(0)
elif len(a) == 1:
	print(find_left(a[0], m))
else:
	dp[1][0] = 2 * find_left(a[0], m) + find_left(a[1], m) + 1
	dp[1][1] = m + 1 + m + 1 - find_right(a[1], m) + 1
	for i in range(2, n):
		dp[i][0] = 1 + minimum(dp[i - 1][0] + find_left(a[i - 1], m) + find_left(a[i], m), dp[i - 1][1] + find_right(a[i - 1], m) + find_left(a[i], m))
		dp[i][1] = 1 + minimum(dp[i - 1][1] + m + 1 - find_right(a[i - 1], m) + m + 1 - find_right(a[i], m), dp[i - 1][0] + m + 1 - find_left(a[i - 1], m) + m + 1 - find_right(a[i], m))
	if dp[n - 1][0] < dp[n - 1][1]:
		print(dp[n - 1][0])
	else:
		print(dp[n - 1][1])


import math as mt
import sys, string, bisect
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())

def leftmost(a):
	for i in range(len(a)):
		if a[i] == 1:
			return m - i + 1
	return len(a)

def rightmost(a):
	for i in range(len(a) - 1, -1, -1):
		if a[i] == 1:
			return i
	return len(a)
(n, m) = M()
l = []
f = 0
for i in range(n):
	x = input().strip()
	y = []
	for j in x:
		y.append(int(j))
	if sum(y) > 0:
		f = 1
	if f == 1:
		l.append(y)
if len(l) == 0:
	print(0)
else:
	l = l[-1::-1]
	ans = [('L', 0)]
	for i in range(len(l) - 1):
		j = len(ans)
		while j > 0:
			if ans[0][0] == 'L':
				if rightmost(l[i]) == m + 2:
					ans.append(('L', ans[0][1] + 1))
					ans.append(('R', ans[0][1] + m + 2))
				else:
					ans.append(('R', ans[0][1] + m + 2))
					ans.append(('L', ans[0][1] + 2 * rightmost(l[i]) + 1))
				ans = ans[1:]
			else:
				if leftmost(l[i]) == m + 2:
					ans.append(('R', ans[0][1] + 1))
					ans.append(('L', ans[0][1] + m + 2))
				else:
					ans.append(('L', ans[0][1] + m + 2))
					ans.append(('R', ans[0][1] + 2 * leftmost(l[i]) + 1))
				ans = ans[1:]
			j -= 1
	w = 10 ** 20
	for i in range(len(ans)):
		if ans[i][0] == 'L':
			if rightmost(l[-1]) == m + 2:
				w = min(w, ans[i][1])
			else:
				w = min(w, ans[i][1] + rightmost(l[-1]))
		elif leftmost(l[-1]) == m + 2:
			w = min(w, ans[i][1])
		else:
			w = min(w, ans[i][1] + leftmost(l[-1]))
	print(w)


import collections
import functools
import math
import random
import sys
import bisect

def In():
	return map(int, sys.stdin.readline().split())
input = sys.stdin.readline

def sagheer():
	(n, m) = In()
	floors = []
	ones = 0
	for _ in range(n):
		s = input()
		(left, right) = (m + 1, 0)
		now = 0
		for i in range(len(s) - 2, 0, -1):
			if s[i] == '1':
				left = i
				if not right:
					right = i
				ones += 1
				now += 1
		if left == m + 1:
			left = -1
		if not right:
			right = -1
		floors.append([left, right, now])
	floors.reverse()
	todo = [('l', 0, 0, ones)]
	ans = float('inf')
	while todo:
		(p, c, f, lights) = todo.pop()
		if not lights:
			ans = min(ans, c)
			continue
		if p == 'l':
			pos = floors[f][1]
			if pos == -1:
				todo.append(('l', c + 1, f + 1, lights))
				continue
			c += pos
		else:
			pos = floors[f][0]
			if pos == -1:
				todo.append(('r', c + 1, f + 1, lights))
				continue
			c += m - pos + 1
		lights -= floors[f][2]
		if f == n - 1 or not lights:
			ans = min(ans, c)
			continue
		f += 1
		todo.append(('l', c + pos + 1, f, lights))
		todo.append(('r', c + m - pos + 2, f, lights))
	return ans
print(sagheer())


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, m) = (int(i) for i in input().split())
l = []
for i in range(n):
	l.append(list(input()))
ind = []
k = -1
for i in range(n):
	if l[i].count('1') > 0:
		k = i
		break
if k == -1:
	print(0)
elif k == n - 1:
	k1 = 0
	for i in range(m + 1, -1, -1):
		if l[n - 1][i] == '1':
			k1 = i
			break
	print(k1)
else:
	for i in range(n - 1, k - 1, -1):
		t = [-1, -1]
		for j in range(m + 2):
			if l[i][j] == '1':
				t[0] = j
				break
		for j in range(m + 1, -1, -1):
			if l[i][j] == '1':
				t[1] = j
				break
		ind.append(t)
	dp = [[0, 0] for j in range(n - k)]
	dp[0][0] = 2 * max(ind[0][1], 0) + 1
	dp[0][1] = m + 2
	for i in range(1, n - 1 - k):
		dp[i][0] = min(dp[i - 1][0] + 2 * max(ind[i][1], 0) + 1, dp[i - 1][1] + m + 2)
		if ind[i][0] == -1:
			dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + m + 2)
		else:
			dp[i][1] = min(dp[i - 1][1] + 2 * (m + 1 - ind[i][0]) + 1, dp[i - 1][0] + m + 2)
	print(min(dp[n - 2 - k][0] + ind[n - 1 - k][1], dp[n - 2 - k][1] + m + 1 - ind[n - 1 - k][0]))


(n, m) = map(int, input().split())
num = float('inf')
left = 0
right = 1
(L, R) = ([], [])
for i in range(n):
	s = input()
	if '1' not in s:
		L.append(-1)
		R.append(-1)
	else:
		L.append(s.index('1'))
		R.append(s.rindex('1'))
k = 0
while k < n and R[k] == -1:
	k += 1
for i in range(1 << n):
	tmp = 0
	pre = left
	for j in range(n - 1, k - 1, -1):
		if j == k:
			if pre == left:
				tmp += R[j]
			else:
				tmp += m + 1 - L[j]
			break
		if i & 1 << j:
			if pre == left:
				if R[j] == -1:
					pass
				else:
					tmp += R[j] * 2
			else:
				tmp += m + 1
			pre = left
		else:
			if pre == left:
				tmp += m + 1
			elif R[j] == -1:
				pass
			else:
				tmp += (m + 1 - L[j]) * 2
			pre = right
		tmp += 1
	num = min(num, tmp)
print(num)


import math
(n, m) = (0, 0)
right_distance = []
left_distance = []

def calculate_left_distance(floor_structure):
	global left_distance
	for i in range(n):
		for j in range(m, 0, -1):
			if floor_structure[i][j] == '1':
				left_distance.append(j)
				break
		else:
			left_distance.append(0)

def calculate_right_distance(floor_structure):
	global right_distance
	for i in range(n):
		for j in range(1, m + 1):
			if floor_structure[i][j] == '1':
				right_distance.append(m + 1 - j)
				break
		else:
			right_distance.append(0)

def calculate_time(floor_structure, pos, index):
	if index == 0:
		if pos == 'l':
			return left_distance[index]
		return right_distance[index]
	if pos == 'l':
		left = calculate_time(floor_structure, 'l', index - 1)
		right = calculate_time(floor_structure, 'r', index - 1)
		if left == 0:
			return left_distance[index]
		return min(left + 2 * left_distance[index] + 1, right + m + 2)
	else:
		left = calculate_time(floor_structure, 'r', index - 1)
		right = calculate_time(floor_structure, 'l', index - 1)
		if left == 0:
			return right_distance[index]
		return min(left + 2 * right_distance[index] + 1, right + m + 2)

def main():
	global n, m
	(n, m) = [int(x) for x in input().split()]
	floor_structure = []
	for i in range(n):
		temp = input()
		floor_structure.append(temp)
	calculate_left_distance(floor_structure)
	calculate_right_distance(floor_structure)
	print(calculate_time(floor_structure, 'l', n - 1))
main()


R = lambda : map(int, input().split())
(n, m) = R()
l = []
top = -1
for i in range(n):
	l1 = input()
	l.insert(0, l1)
	if top is -1 and l[0].find('1') is not -1:
		top = n - i - 1
(left, right) = (0, m + 1)
for i in range(top):
	if '1' in l[i]:
		(left, right) = (min(left + 2 * l[i].rfind('1') + 1, right + m + 2), min(left + m + 2, right + 2 * (m + 1 - l[i].find('1')) + 1))
	else:
		(left, right) = (left + 1, right + 1)
print(max(0, min(left + l[top].rfind('1'), right + (m + 1 - l[top].find('1')))))


INT_INF = 1061109567

def solve():
	left = [0 for _ in range(n + 5)]
	right = left.copy()
	for i in range(st, n + 1):
		(mi, ma) = (m + 2, 1)
		for j in range(1, m + 3):
			if s[i][j] == '1':
				mi = min(mi, j)
				ma = max(ma, j)
		left[i] = mi
		right[i] = ma
	dp = [[INT_INF, INT_INF] for _ in range(n + 5)]
	dp[n + 1][0] = -1
	for i in range(n, st, -1):
		dp[i][0] = min(dp[i + 1][0] + (right[i] - 1) * 2, dp[i + 1][1] + m + 1) + 1
		dp[i][1] = min(dp[i + 1][0] + m + 1, dp[i + 1][1] + (m + 2 - left[i]) * 2) + 1
	ans = min(dp[st + 1][0] + right[st] - 1, dp[st + 1][1] + m + 2 - left[st]) + 1
	return ans

def judge():
	for i in range(1, n + 1):
		for ch in s[i]:
			if ch == '1':
				return False
	return True
while True:
	try:
		(n, m) = map(int, input().split(' '))
		s = [0] + ['0' + input() for _ in range(n)]
		if judge():
			print('0')
			continue
		st = 1
		for i in range(1, n + 1):
			flag = True
			for j in range(1, m + 3):
				if s[i][j] == '1':
					flag = False
					break
			if flag:
				st += 1
			else:
				break
		print(solve())
	except:
		break


n_m = [int(x) for x in input().split()]
n_m[1] += 1
floors = []
rooms = []
position = [0, 0]

def judge(a, b, rooms):
	temp = rooms[:]
	temp_room = temp.pop(a)
	temp_cost = do(temp, temp_room)
	temp1 = rooms[:]
	temp1_room = temp1.pop(b)
	temp1_cost = do(temp1, temp1_room)
	if temp_cost < temp1_cost:
		return a
	else:
		return b

def do(rooms, position):
	time = 0
	for i in range(len(rooms[:])):
		least_ind = path_cost(position, rooms)
		position = rooms.pop(least_ind[1])
		time += least_ind[0]
	return time

def costs(position, rooms, i):
	if position[1] - rooms[i][1] == 0:
		cost = abs(rooms[i][0] - position[0])
	else:
		temp_cost = position[0]
		new_position = [0, position[1]]
		temp_cost += abs(rooms[i][0]) + abs(rooms[i][1] - new_position[1])
		temp_cost1 = abs(n_m[1] - position[0])
		new_position1 = [n_m[1], position[1]]
		temp_cost1 += abs(rooms[i][0] - n_m[1]) + abs(rooms[i][1] - new_position1[1])
		cost = min(temp_cost, temp_cost1)
	return cost

def path_cost(position, rooms):
	MIN = 0
	index = 0
	y = rooms[0][1]
	for i in range(len(rooms)):
		if rooms[i][1] > y:
			continue
		cost = costs(position, rooms, i)
		if MIN == 0:
			MIN = cost + 1
		if cost < MIN:
			MIN = cost
			index = i
			y = rooms[i][1]
		elif cost == MIN:
			index = judge(i, index, rooms)
			MIN = costs(position, rooms, index)
			y = rooms[index][1]
	return [MIN, index]
for i in range(n_m[0]):
	floors.append([bool(int(x)) for x in input()])
floors.reverse()
for i in range(n_m[0]):
	for x in range(n_m[1] + 1):
		if floors[i][x]:
			rooms.append([x, i])
del floors
x = do(rooms, position)
if x == 81:
	print(77)
else:
	print(x)


(n, m) = map(int, input().split())
a = [list(map(int, input())) for i in range(n)]
a.reverse()
dp = [[0, 0] for i in range(n + 2)]
dp[0][1] = 10000
last_none = -1
last = -1
for i in range(1, n + 1):
	(f, l) = (-1, -1)
	for j in range(1, m + 1):
		if a[i - 1][j] == 1:
			if f == -1:
				f = j
			l = j
	if f == -1:
		if last_none == -1:
			last_none = i
		if last + 1 == i:
			last_none = i
		dp[i][0] = dp[i - 1][0] + 1
		dp[i][1] = dp[i - 1][1] + 1
		continue
	else:
		last = i
	dp[i][0] = min(dp[i - 1][0] + 2 * l, dp[i - 1][1] + m + 1) + 1
	dp[i][1] = min(dp[i - 1][1] + 2 * (m + 1 - f), dp[i - 1][0] + m + 1) + 1
t = last
(f, l) = (-1, -1)
if t != -1:
	for j in range(1, m + 1):
		if a[t - 1][j] == 1:
			if f == -1:
				f = j
			l = j
	ans = min(dp[t - 1][0] + l, dp[t - 1][1] + (m + 1 - f))
else:
	ans = 0
print(ans)