题目描述

Bocchi the Builder just finished constructing her latest project: a laneway consisting of two rows of white equilateral triangular tiles. However, at the last moment, disaster struck! She accidentally spilled black paint on some of the tiles. Now, some of the tiles are wet and the other tiles are dry. Bocchi must place warning tape around the perimeters of all wet areas. Can you help her determine how many metres of tape she needs?

The first triangular tile will point upwards. Each pair of adjacent tiles (that is, tiles that share a common side) will point in opposite directions. Each tile has a side length of $1$ metre.

输入格式

The first line of input will consist of one positive integer $C$, representing the number of columns.

The next two lines will each consist of $C$ integers separated by spaces. Each integer represents the colour of a tile along the laneway, with 1 indicating that the tile is black (wet) and 0 indicating that the tile is white (dry).

The following table shows how the available 15 marks are distributed:

输出格式

Output a single integer representing the length of tape Bocchi needs,in metres.

题目大意

设计师 Bocchi 刚刚完成一个工程：一个由上下两部分组成的巷道，每一部分都由一排边长为 $1$ 米的三角形构成。不过这项工程还有一点小瑕疵：有一部分三角形被涂成了黑色，它们的油漆还没干，所以暂时不能使用。Bocchi 想用警戒线将这部分三角形围住，请问至少需要几米长的警戒线才能围上。

一个图形由上下均由 $C$ 个三角形构成。

你需要实现一个程序：

输入一个整数 $C$（$1 \leq C \leq 2 \times 10^5$），接下来两行，每行 $C$ 个数字，1 表示黑色三角形，0 表示白色三角形，请你求出围上黑色三角形需要多少米栅栏。

5
1 0 1 0 1
0 0 0 0 0

9

7
0 0 1 1 0 1 0
0 0 1 0 1 0 0

11

提示

本题采用捆绑测试。

• Subtask $1$（$3$ points）：$C \leq 2 \times 10^3$，黑色三角形不相邻，第二行全部为白色三角形。
• Subtask $2$（$3$ points）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行全部为白色三角形。
• Subtask $3$（$5$ points）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行可能有黑色三角形。
• Subtask $4$（$4$ points）：$C \leq 2 \times 10^5$，黑色三角形可能相邻，第二行可能有黑色三角形。

样例 $1$ 图解：

样例 $2$ 图解：