Sofas

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are renovating their living room.

Marichka prepared a placement plan for all the furniture except the sofa. She entrusted this task to Zenyk, who loves sofas very much and wants to place as many of them as possible.

The room is square in size and consists of \(n \times n\) unit squares. The furniture placement plan can be represented as a matrix \(A\) of \(n\) rows and \(n\) columns, where the value \(A_{ij}\) is equal to 1 if the corresponding unit square is already filled with furniture, or 0 if not.

Zenyk wants to place as many sofas of size \(1 \times (n-1)\) or \((n-1) \times 1\) as possible. Your task is to help him find this maximum number.

Note that sofas cannot intersect; they must be placed parallel to the walls without occupying already taken space; the boundaries of the sofas must coincide with the boundaries of the unit squares.

Input

The first line contains a single integer \(n\) — the size of the walls.

The next \(n\) lines each contain \(n\) characters, 0 or 1, without spaces — the matrix \(A\). The character 1 means that the corresponding square is occupied, 0 means it is free.

Output

In a single line, print a single integer — the maximum number of sofas.

Constraints

\(3 \le n \le 50\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 111 000 000	3

Input (stdin) сopy	Output (stdout) сopy
3 000 100 101	3

Input (stdin) сopy	Output (stdout) сopy
4 0000 0000 0000 0000	5

Notes

In the first example, it is optimal to place three sofas as follows (identical letters denote sofa positions):

In the second example, three sofas can also be placed:

In the third example, 5 sofas can be placed: