Electronical Plate

A square grid is carved into the top of a square plate. Each place where two gridlines cross is called a node, so the plate holds n × n nodes arranged in n rows and n columns. A node lying in the outermost row or column is a boundary node.

Some nodes hold pins. We want to connect pins to the boundary of the plate with electronic circuits laid along the grid, subject to these rules:

• A circuit runs only along the gridlines, moving between orthogonally adjacent nodes; it can never run diagonally.
• No two circuits may share any point. In particular, two circuits may not overlap on the same gridline segment, and they may not pass through the same node. Equivalently, all circuits are node-disjoint.
• A circuit may not run along the boundary: it must stop the moment it first reaches a boundary node.
• A circuit may neither pass through nor end on a node that holds another pin.

A pin that already sits on a boundary node is considered connected and needs no circuit.

Figure. A plate with pins (center) and an example of valid circuit connections (right).

Determine the maximum number of pins that can be connected to the boundary by circuits (equivalently, the maximum number of node-disjoint circuits that can be laid). Pins that are already on the boundary are not counted, because they need no circuit.

The first line contains an integer n (3 ≤ n ≤ 15).

Each of the next n lines contains n digits separated by single spaces. Each digit is 1 or 0: a 1 marks a node that holds a pin, and a 0 marks an empty node. The lines are given from the top row to the bottom row, and within each line from the leftmost column to the rightmost column.

Print a single integer: the maximum number of pins that can be connected to the boundary using node-disjoint circuits that obey all of the rules above.