Bishops

In chess, a bishop can move any number of squares diagonally and can capture a piece on the same diagonal. In the figure below, the bishop at B can capture pieces on the cells marked O.

Some cells of the square chessboard cannot contain a bishop. In the figure below, the shaded cells are such cells. A bishop cannot be placed on those cells, but it may pass through them while moving diagonally.

If bishops are placed so that no two can capture each other, the board above can hold at most 7 bishops as shown below.

The size of the chessboard is the number of cells along one side. Given the board size and whether each cell can contain a bishop, find the maximum number of bishops that can be placed so that no two attack each other.

The first line contains the board size N. N is a positive integer no greater than 10.

The next N lines describe the board, one row per line. Each row contains N integers separated by spaces. A 1 means a bishop can be placed on that cell, and a 0 means it cannot.

Print the maximum number of bishops that can be placed on the given board so that no two attack each other.