P15663 [ICPC 2025 Jakarta R] International Olympiad in ICPC

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.

$\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 ```