Tape Around Wet Areas

Bocchi the Builder has constructed a laneway consisting of two rows of white equilateral triangular tiles. Unfortunately, she accidentally spilled black paint on some of the tiles, making them wet. She now needs to place warning tape around the perimeters of all contiguous wet areas. Your task is to help Bocchi determine how many metres of tape she needs.

The tiling is arranged in two rows with n columns. The top row is given as a string of 0s and 1s, where 1 indicates a wet tile and 0 a dry tile. The bottom row is provided in the same format. To form the laneway, the two rows are laid out such that the tile in the top row at column i and the tile in the bottom row at column i are placed one above the other, but the bottom row is shifted so that the two rows are complementary. In particular, the top row is arranged so that the first tile points upwards and then alternates in orientation (i.e. upward, downward, upward, …), while the bottom row’s first tile is oriented in the opposite direction to the top row’s first tile (i.e. downward, upward, downward, …).

All tiles are equilateral triangles with a side length of $1$ metre. Hence, each tile has a perimeter of $3$ metres. However, whenever two wet tiles share a common side, that side should not be taped. In this configuration two tiles share a side if:

• They are adjacent horizontally in the same row (i.e. columns i and i+1).
• They are one above the other in the two rows at the same column (the design guarantees that the two overlapping tiles have opposite orientations and share a side).

The total length of tape needed is thus given by the sum of the individual perimeters of all wet tiles minus twice the number of pairs of wet tiles that share a side (since a shared side is counted in both tiles’ perimeters). That is, if W is the number of wet tiles and S is the number of adjacent wet-pairs (counted once per shared side), the required tape is:

inputFormat

The input consists of three lines:

1. An integer n representing the number of columns in each row (where n \ge 1).
2. A string of n characters (each either 0 or 1) describing the top row of tiles (with 1 indicating a wet tile).
3. A string of n characters (each either 0 or 1) describing the bottom row of tiles.

You may assume that the input is valid.

outputFormat

Output a single integer, the total number of metres of tape required.

sample

3
010
000

3