考虑一个走廊,它可以表示为具有 $$$2$$$ 行和 $$$n$$$ 列的矩阵。我们将第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格表示为 $$$(i, j)$$$。单元格 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 之间的距离为 $$$|i_1 - i_2| + |j_1 - j_2|$$$。
牢房$$$(1, 1)$$$中有一个清洁机器人。走廊的一些牢房是干净的,其他牢房是脏的(有机器人的牢房是干净的)。您想要清洁走廊,因此您将启动机器人来执行此操作。
机器人启动后,工作原理如下。当至少一个单元格脏时,机器人会在脏单元格中选择最接近的(与其当前单元格),移动到那里并清洁它(因此该单元格不再脏)。清洁完一个单元后,机器人会再次找到距离当前单元最近的脏单元,依此类推。重复这个过程,直到整个走廊都干净为止。
然而,机器人的程序中存在一个严重的错误。如果在某个时刻,有多个最接近(距离机器人当前位置)的脏单元,则机器人会发生故障。
您希望以机器人不会发生故障的方式清洁走廊。在启动机器人之前,您可以自己清理一些(可能是零)脏的单元格。然而,当你有这个漂亮、聪明(但有缺陷)的机器人来做这件事时,你不想自己做太多脏活。请注意,您不能弄脏干净的电池。
计算在启动机器人之前可以留下脏东西的最大可能数量,这样它就不会发生故障。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 走廊中的柱数。
接下来是两行,表示走廊的 $$$1$$$-st 和 $$$2$$$-nd 行。这些行每行包含 $$$n$$$ 个字符,其中 0 表示干净单元格,1 表示脏单元格。机器人 $$$(1, 1)$$$ 的起始单元是干净的。
输出
打印一个整数——在启动机器人之前可以保留脏的最大可能数量的单元格,这样它就不会发生故障。
示例
输入 #1
2 01 11
输出 #1
2
输入 #2
2 01 01
输出 #2
2
输入 #3
4 0101 1011
输出 #3
4
输入#4
4 0000 0000
输出#4
0
输入 #5
5 00011 10101
输出 #5
4
输入 #6
6 011111 111111
输出 #6
8
输入#7
10 0101001010 1010100110
输出 #7
6
注意
在第一个示例中,您可以清理单元格 $$$(1, 2)$$$,因此机器人的路径为 $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$。
在第二个示例中,您可以保持走廊不变,因此机器人的路径为 $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$$$。
在第三个示例中,您可以清理单元格 $$$(1, 2)$$$,因此机器人的路径为 $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$$$。
在第四个示例中,走廊已经干净了。也许您之前已经启动了机器人?