#000016

molekuli

A chemist works on the project of creating a super-molecule consisting of four given equal-sized molecules. A molecule is represented as the sequence of atoms that construct it. Atoms are represented with big Latin alphabet letters. A model of a super-molecule can be represented in two-dimensional space in such a way that any two of four given molecules are vertical and the other two are horizontal. Every horizontally placed molecule has exactly one common (overlapping) atom with the other two vertical molecules. Certain rules of putting molecules together apply:


- Every molecule must be used exactly once
- Any one of the four given molecules can be placed in any horizontal or any vertical line of a super-molecule
- If a molecule is placed horizontally, then it has to be oriented from left to right
- If a molecule is placed vertically, then it has to be oriented from top to bottom
- The surface of a rectangle in the center of the molecule needs to be as large as possible. This surface will always be greater that zero. (The common atom doesn't count in the rectangle's side length)
- The first and last atom of a molecule can't be used as a common atom.


Your task is to help the chemist make a super-molecule according to the rules given above.


InputThe first line of standard input contains a number N (5 <= N <= 20), which represents a molecule's length. In each of the next 4 lines there will be descriptions of given molecules. These descriptions are made of N big Latin alphabet letters with no spaces between them.

OutputTo the standard output you shoud write the maximum surface of a super-molecule which satisfies the stated rules. If there is no such molecule, then write "0" in the standard output (quotes are here only for clarity, don't write them).

Input:
8
ANJBCDSP
CBNIOKIA
JKDCOOQO
RTICIFQE

Output:
9

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.