{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nSagheer 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.\n\nNote 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."},{"iden":"input","content":"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.\n\nThe 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.\n\nThe first and last characters of each string represent the left and the right stairs, respectively, so they are always 0."},{"iden":"output","content":"Print a single integer — the minimum total time needed to turn off all the lights."},{"iden":"examples","content":"Input\n\n2 2\n0010\n0100\n\nOutput\n\n5\n\nInput\n\n3 4\n001000\n000010\n000010\n\nOutput\n\n12\n\nInput\n\n4 3\n01110\n01110\n01110\n01110\n\nOutput\n\n18"},{"iden":"note","content":"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.\n\nIn 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.\n\nIn the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor."}],"translated_statement":[{"iden":"statement","content":"有些人离开工作场所时会忘记关灯，这是资源的浪费。作为 DHBW 的管理员，Sagheer 会等到所有学生和教授离开教学楼后，再下去关闭所有灯光。\n\n该建筑共有 #cf_span[n] 层，每层左右两侧均有楼梯。每层有 #cf_span[m] 个房间，排列在一条直线上，一条走廊连接左右楼梯并经过所有房间。换句话说，该建筑可以表示为一个包含 #cf_span[n] 行和 #cf_span[m + 2] 列的矩形，其中第一列和最后一列表示楼梯，中间的 #cf_span[m] 列表示房间。\n\nSagheer 初始位于底层的左侧楼梯。他希望以如下方式关闭所有灯光：在前往上一层之前，必须确保当前所在楼层的所有灯都已关闭。当然，Sagheer 必须进入房间才能关闭其中的灯。Sagheer 爬一层楼梯或在同一层内从当前房间/楼梯移动到相邻的房间/楼梯均需花费一分钟。他在当前所在房间内关闭灯无需时间。请帮助 Sagheer 找到关闭所有灯所需的最少总时间。\n\n注意：Sagheer 无需返回起始位置，也无需访问灯光已关闭的房间。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 15] 且 #cf_span[1 ≤ m ≤ 100]），分别表示楼层数和每层房间数。\n\n接下来的 #cf_span[n] 行描述建筑结构。每行是一个长度为 #cf_span[m + 2] 的二进制字符串，表示一层（左侧楼梯，接着 #cf_span[m] 个房间，然后是右侧楼梯），其中 #cf_span[0] 表示灯已关闭，#cf_span[1] 表示灯已开启。楼层从上到下给出，因此最后一行代表底层。\n\n每行字符串的第一个和最后一个字符分别表示左侧和右侧楼梯，它们始终为 #cf_span[0]。\n\n请输出一个整数——关闭所有灯所需的最少总时间。\n\n在第一个示例中，Sagheer 将前往底层的第 #cf_span[1] 个房间，然后使用左侧或右侧楼梯前往第二层的第 #cf_span[2] 个房间。\n\n在第二个示例中，他将前往底层的第四个房间，使用右侧楼梯，前往第二层的第四个房间，再次使用右侧楼梯，然后前往顶层的第二个房间。\n\n在第三个示例中，他将在每一层沿着走廊来回走动，在左右楼梯间交替移动。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 15] 且 #cf_span[1 ≤ m ≤ 100]），分别表示楼层数和每层房间数。接下来的 #cf_span[n] 行描述建筑结构。每行是一个长度为 #cf_span[m + 2] 的二进制字符串，表示一层（左侧楼梯，接着 #cf_span[m] 个房间，然后是右侧楼梯），其中 #cf_span[0] 表示灯已关闭，#cf_span[1] 表示灯已开启。楼层从上到下给出，因此最后一行代表底层。每行字符串的第一个和最后一个字符分别表示左侧和右侧楼梯，它们始终为 #cf_span[0]。"},{"iden":"output","content":"请输出一个整数——关闭所有灯所需的最少总时间。"},{"iden":"examples","content":"输入\n2 2\n0010\n0100\n输出\n5\n\n输入\n3 4\n00100000\n00100000\n10010000\n输出\n12\n\n输入\n4 3\n01110\n01110\n01110\n01110\n输出\n18"},{"iden":"note","content":"在第一个示例中，Sagheer 将前往底层的第 #cf_span[1] 个房间，然后使用左侧或右侧楼梯前往第二层的第 #cf_span[2] 个房间。在第二个示例中，他将前往底层的第四个房间，使用右侧楼梯，前往第二层的第四个房间，再次使用右侧楼梯，然后前往顶层的第二个房间。在第三个示例中，他将在每一层沿着走廊来回走动，在左右楼梯间交替移动。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the number of floors and $ m $ the number of rooms per floor. The building is modeled as a grid with $ n $ rows (floors, indexed top to bottom: floor $ 0 $ is top, floor $ n-1 $ is ground) and $ m+2 $ columns (left stair, $ m $ rooms, right stair). Each cell $ (i, j) $, for $ i \\in \\{0, \\dots, n-1\\} $, $ j \\in \\{0, \\dots, m+1\\} $, holds a binary value: 1 if the light is on, 0 if off. The first and last columns ($ j=0 $ and $ j=m+1 $) are stairs and always 0.\n\nDefine $ L_i = \\min\\{ j \\in \\{1, \\dots, m\\} \\mid \\text{light at } (i,j) = 1 \\} $ if any light is on on floor $ i $, else $ \\infty $,  \nand $ R_i = \\max\\{ j \\in \\{1, \\dots, m\\} \\mid \\text{light at } (i,j) = 1 \\} $ if any light is on on floor $ i $, else $ -\\infty $.\n\nLet $ k = \\max\\{ i \\in \\{0, \\dots, n-1\\} \\mid L_i \\neq \\infty \\} $ be the highest floor (lowest index) with at least one light on.\n\nSagheer starts at $ (n-1, 0) $ (ground floor, left stair). He must visit every floor $ i \\in \\{0, \\dots, k\\} $ that has at least one light on, in order from bottom to top (i.e., from floor $ n-1 $ up to floor $ k $), and on each such floor $ i $, he must traverse from his entry point (left or right stair) to the leftmost and rightmost lit room on that floor, and then proceed upward.\n\nOn floor $ i $, if he enters at left stair ($ j=0 $), the cost to cover all lit rooms is $ R_i - 0 $, and he exits at right stair.  \nIf he enters at right stair ($ j=m+1 $), the cost is $ (m+1) - L_i $, and he exits at left stair.\n\nHe may choose, for each floor $ i \\in \\{0, \\dots, k\\} $, whether to enter from left or right, but his entry point on floor $ i $ must match the exit point from floor $ i+1 $, since he moves vertically between stairs.\n\nLet $ dp[i][e] $ be the minimum time to turn off all lights on floors $ i $ to $ k $, starting at floor $ i $ at stair $ e \\in \\{0, 1\\} $ (0 = left, 1 = right), having already turned off all lights on floors above $ i $.\n\nBase case:  \nFor $ i = k $:  \n- $ dp[k][0] = R_k $  \n- $ dp[k][1] = m+1 - L_k $\n\nRecurrence for $ i < k $:  \nIf floor $ i $ has no lights, then $ dp[i][e] = dp[i+1][e] + 1 $ (just go up one floor).  \nOtherwise:  \n- $ dp[i][0] = \\min( R_i + 1 + dp[i+1][1],\\ (m+1 - L_i) + 1 + dp[i+1][0] ) $  \n  (enter left: go to $ R_i $, then up to next floor’s right; or enter left, go to $ L_i $, then to $ R_i $, then up to next floor’s left — but since he must cover all, and $ L_i \\leq R_i $, the path is $ 0 \\to R_i $, cost $ R_i $, then up to next floor’s right)  \nWait — correction:\n\nActually, if he enters floor $ i $ at left stair (0), he must go to $ R_i $ to cover all lights (since $ L_i \\leq R_i $, and he must visit both ends), so path: $ 0 \\to R_i $, cost $ R_i $, then he exits at right stair.  \nSimilarly, if he enters at right stair (1), he goes to $ L_i $, cost $ (m+1) - L_i $, exits at left stair.\n\nSo for floor $ i $ with lights:  \n- If entering at left: cost = $ R_i $, exit at right  \n- If entering at right: cost = $ m+1 - L_i $, exit at left\n\nThen he moves up one floor: cost 1, to the corresponding stair on floor $ i+1 $.\n\nThus:\n\nFor $ i \\in \\{0, \\dots, k-1\\} $:  \n- If floor $ i $ has lights:  \n  $ dp[i][0] = R_i + 1 + dp[i+1][1] $  \n  $ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $  \n- If floor $ i $ has no lights:  \n  $ dp[i][0] = 1 + dp[i+1][0] $  \n  $ dp[i][1] = 1 + dp[i+1][1] $\n\nBut Sagheer starts at $ (n-1, 0) $. So we must compute $ dp[n-1][0] $, but only if floor $ n-1 $ has lights. If not, we must go up until we hit the first floor with lights.\n\nActually, let $ k $ be the highest floor (lowest index) with any light on. Then Sagheer must go from floor $ n-1 $ up to floor $ k $, turning off lights only on floors $ k $ to $ n-1 $.\n\nSo define the relevant floors: let $ k $ be the smallest index $ i \\in \\{0, \\dots, n-1\\} $ such that $ L_i \\neq \\infty $. Then Sagheer must visit all floors from $ n-1 $ down to $ k $, i.e., in order: $ n-1, n-2, \\dots, k $.\n\nBut the problem says: “he will not go upstairs until all lights in the floor he is standing at are off.” So he must finish a floor before going up.\n\nThus, he starts at floor $ n-1 $. He must turn off all lights on floor $ n-1 $, then go to floor $ n-2 $, etc., up to floor $ k $.\n\nSo we process floors from bottom to top: $ i = n-1, n-2, \\dots, k $.\n\nLet $ dp[i][e] $ = minimum time to turn off all lights on floors $ i $ to $ n-1 $, starting at floor $ i $ at stair $ e \\in \\{0,1\\} $, and ending at the exit stair on floor $ i $.\n\nThen, for $ i = n-1 $:  \n- If lights exist:  \n  $ dp[n-1][0] = R_{n-1} $  \n  $ dp[n-1][1] = m+1 - L_{n-1} $  \n- Else:  \n  $ dp[n-1][0] = 0 $  \n  $ dp[n-1][1] = 0 $\n\nFor $ i $ from $ n-2 $ down to $ k $:  \nIf floor $ i $ has lights:  \n- $ dp[i][0] = R_i + 1 + dp[i+1][1] $  \n- $ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $  \nIf floor $ i $ has no lights:  \n- $ dp[i][0] = 1 + dp[i+1][0] $  \n- $ dp[i][1] = 1 + dp[i+1][1] $\n\nBut if there are no lights on floor $ i $, he just walks from his entry stair to the next floor’s same stair? No — he must go up, but he can choose to go up from either stair? No — he enters floor $ i $ at stair $ e $, and since there are no lights, he just goes up from that same stair to floor $ i+1 $’s same stair. So cost is 1 (to go up), and he exits at same stair on floor $ i+1 $.\n\nBut wait — he is going **up** from floor $ i $ to floor $ i+1 $. But we are iterating from bottom up: floor $ n-1 $ is bottom. So when we are at floor $ i $, we are processing it before floor $ i+1 $ (which is above). But in our DP, we go from $ i = n-2 $ down to $ k $, and use $ dp[i+1] $, which is the floor above.\n\nActually, we are going from bottom to top in physical space, but DP is computed bottom-up: we start at bottom floor, then move to floor above it, etc.\n\nSo the recurrence is correct.\n\nBut Sagheer starts at $ (n-1, 0) $. So the answer is $ dp[n-1][0] $, but only if floor $ n-1 $ has lights. If not, he must go up.\n\nActually, we need to find the lowest floor $ k $ with any light on. Then Sagheer must go from floor $ n-1 $ to floor $ k $, turning off lights only on floors from $ k $ to $ n-1 $.\n\nSo we can define $ k = \\min \\{ i \\in \\{0, \\dots, n-1\\} \\mid \\exists j \\in \\{1,\\dots,m\\}, \\text{light}(i,j)=1 \\} $\n\nIf no such $ k $, return 0.\n\nThen, we compute $ dp[i][e] $ for $ i = k, k+1, \\dots, n-1 $, in reverse order (from $ n-1 $ down to $ k $).\n\nBut we must account for the cost of ascending from floor $ n-1 $ to floor $ k $, if $ k < n-1 $. That is, if there are empty floors above $ k $, he must walk up through them.\n\nSo we should compute $ dp[i][e] $ for all floors $ i \\in \\{k, k+1, \\dots, n-1\\} $, and start from $ i = n-1 $.\n\nDefine for $ i \\in \\{k, k+1, \\dots, n-1\\} $:\n\n- If $ i = n-1 $:  \n  - If floor $ n-1 $ has lights:  \n    $ dp[n-1][0] = R_{n-1} $  \n    $ dp[n-1][1] = m+1 - L_{n-1} $  \n  - Else:  \n    $ dp[n-1][0] = 0 $  \n    $ dp[n-1][1] = 0 $\n\n- For $ i $ from $ n-2 $ down to $ k $:  \n  - If floor $ i $ has lights:  \n    $ dp[i][0] = R_i + 1 + dp[i+1][1] $  \n    $ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $  \n  - Else:  \n    $ dp[i][0] = 1 + dp[i+1][0] $  \n    $ dp[i][1] = 1 + dp[i+1][1] $\n\nThen, since Sagheer starts at $ (n-1, 0) $, the answer is $ dp[n-1][0] $.\n\nBut wait — if floor $ n-1 $ has no lights, then $ dp[n-1][0] = 0 $, but he still needs to go up to floor $ k $, which is above? No — $ k $ is the topmost floor with lights, and he starts at bottom. So if $ k < n-1 $, then $ k $ is above $ n-1 $? No — floors are indexed 0 (top) to $ n-1 $ (bottom). So $ k $ is the smallest index (highest floor) with lights. So he starts at floor $ n-1 $ (bottom), and must go **up** to floor $ k $ (which is numerically smaller index).\n\nSo the path is: start at $ (n-1, 0) $, go up to $ (n-2, 0) $, then $ (n-3, 0) $, ..., until $ (k, 0) $, then traverse floor $ k $, then go up? No — he must turn off lights on each floor before going up. So he must traverse floor $ n-1 $, then go up to $ n-2 $, traverse it, etc., up to floor $ k $.\n\nSo the DP above is correct: we start at the bottom floor $ n-1 $, and move upward to $ k $.\n\nThus, the answer is $ dp[n-1][0] $, computed as above.\n\nBut note: if floor $ i $ has no lights, he just goes up from his current stair to the same stair on the floor above. So the DP correctly adds 1 minute to go up.\n\nFinal formal statement:\n\nLet $ n, m \\in \\mathbb{N} $, $ 1 \\leq n \\leq 15 $, $ 1 \\leq m \\leq 100 $.  \nLet $ B \\in \\{0,1\\}^{n \\times (m+2)} $, where $ B[i][0] = B[i][m+1] = 0 $ for all $ i $, and $ B[i][j] \\in \\{0,1\\} $ for $ j \\in \\{1,\\dots,m\\} $.  \nLet $ k = \\min \\{ i \\in \\{0,\\dots,n-1\\} \\mid \\exists j \\in \\{1,\\dots,m\\}, B[i][j] = 1 \\} $. If no such $ i $, return 0.\n\nFor each floor $ i \\in \\{0,\\dots,n-1\\} $, define:  \n- $ L_i = \\min \\{ j \\in \\{1,\\dots,m\\} \\mid B[i][j] = 1 \\} $ if $ \\exists j $ with $ B[i][j] = 1 $, else $ \\infty $  \n- $ R_i = \\max \\{ j \\in \\{1,\\dots,m\\} \\mid B[i][j] = 1 \\} $ if $ \\exists j $ with $ B[i][j] = 1 $, else $ -\\infty $\n\nDefine $ dp[i][e] $ for $ i \\in \\{k, k+1, \\dots, n-1\\} $, $ e \\in \\{0,1\\} $:  \n- $ dp[n-1][0] = \\begin{cases} R_{n-1} & \\text{if } L_{n-1} \\neq \\infty \\\\ 0 & \\text{otherwise} \\end{cases} $  \n- $ dp[n-1][1] = \\begin{cases} m+1 - L_{n-1} & \\text{if } L_{n-1} \\neq \\infty \\\\ 0 & \\text{otherwise} \\end{cases} $\n\nFor $ i $ from $ n-2 $ down to $ k $:  \n- If $ L_i \\neq \\infty $:  \n  $ dp[i][0] = R_i + 1 + dp[i+1][1] $  \n  $ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $  \n- Else:  \n  $ dp[i][0] = 1 + dp[i+1][0] $  \n  $ dp[i][1] = 1 + dp[i+1][1] $\n\nAnswer: $ dp[n-1][0] $\n\nNote: Since Sagheer starts at left stair of ground floor (floor $ n-1 $), we use $ e=0 $.","simple_statement":null,"has_page_source":false}