题目描述

Your university is hosting a competition called the IOI. As an event organiser, you want to create a banner for it. The banner you are preparing can be represented as a $3 \times N$ grid, where each cell will be printed either white or black. Due to printing issues, some of the cells cannot be printed in black.

You start with a white banner, and want to print the word $\texttt{IOI}$ on the banner as follows.

• Form the first letter $\texttt{I}$ by printing a $\textbf{solid}$ rectangle of size $3 \times p$ ($p \geq 1$) in black.
• Form the letter $\texttt{O}$ by printing a rectangular $\textbf{boundary}$ of size $3 \times q$ ($q \geq 3$) in black.
• Form the second letter $\texttt{I}$ by printing a $\textbf{solid}$ rectangle of size $3 \times r$ ($r \geq 1$) in black.

The letter $\texttt{O}$ must be formed between the letters $\texttt{I}$, and there must be $\textbf{at least}$ one column between the letters. It is also required that the width of the letter $\texttt{O}$ is $\textbf{at least}$ the sum of the widths of the letters $\texttt{I}$, i.e. $q \geq p + r$. All other cells not part of the word $\texttt{IOI}$ must remain white.

Determine the maximum number of cells that you can print in black, or tell that it's impossible to print the word $\texttt{IOI}$.

输入格式

The first line contains an integer $N$ ($1 \le N \le 200\;000$), the size of the $3 \times N$ grid.

Each of the next three lines contains $N$ characters representing the cells of the grid.

Each of the $3N$ characters corresponds to a cell and is either $\texttt{.}$ or $\texttt{\#}$, meaning you can or cannot print the cell in black, respectively.

输出格式

A single line representing the maximum number of cells that you can print in black.

If it's impossible to print the word $\texttt{IOI}$, output $-1$ instead.

7
.......
.......
.......

14

6
......
......
......

-1

12
...#....#...
...#.##.#...
...#....#...

22

20
#...##..............
#...##.##....#...#..
#...##..............

39

提示

$\textit{Explanation of Sample 1:}$ You can print your banner in the following way.

  I.OOO.I
  I.O.O.I
  I.OOO.I

$\textit{Explanation of Sample 3:}$ You can print your banner in the following way.

  ..I#OOOO#III
  ..I#O##O#III
  ..I#OOOO#III

$\textit{Explanation of Sample 4:}$ You can print your banner in the following way.

  #III##OOOOOOOOOOO.II
  #III##O##....#..O#II
  #III##OOOOOOOOOOO.II