Silk Scarf Cutting

A precious silk scarf in the form of an equilateral triangle is divided into small unit equilateral triangles. Unfortunately, some of the cells have been damaged by worms. The tailor wants to cut the scarf into two smaller scarves, each having the same shape as the original (i.e. an equilateral triangle), by cutting along the cell boundaries. Moreover, neither piece may include a damaged cell, and the sum of their areas should be maximized.

The original scarf is subdivided uniformly. Each edge is divided into $N$ segments, so that the entire scarf consists of $N^2$ small equilateral triangles. Viewed from top to bottom, the rows have 1, 3, 5, …, $(2N-1)$ cells respectively. We assign coordinates to the cells: the unique cell in the first row is $(1,1)$; the second row’s cells are $(2,1)$, $(2,2)$, $(2,3)$; and so on.

A sub‐scarf (small equilateral triangle) is defined as follows. For an integer $k\ge1$, a sub‐scarf of side length $k$ consists of $k$ rows. The first row contains 1 cell, the second row contains 3 cells, the third row 5 cells, and in general the $k$th row contains $(2k-1)$ cells. The sub‐scarf must be aligned with the original scarf (i.e. with the same orientation).

The cutting conditions are:

1. Both pieces must be equilateral triangles with the same shape as the original.
2. Neither piece may contain any damaged cell.
3. The cuts must follow the boundaries of the unit cells.
4. The sum of the areas (number of unit cells) of the two pieces should be maximized.

Note: The area of a sub‐scarf with side length $k$ is $k^2$.

inputFormat

The first line contains an integer $N$ ($1 \le N \le 10$), indicating the number of divisions on each side of the original scarf.

Each of the next $N$ lines describes a row of the scarf. The $i$th line is a string of length $2i-1$ consisting only of the characters '1' and '0', where '1' denotes an intact cell and '0' indicates a cell damaged by worms.

outputFormat

Output a single integer: the maximum total area (sum of the areas of the two sub‐scarves) that can be obtained according to the cutting conditions. If it is impossible to obtain two valid pieces, output 0.

sample

1
1

0