Minimum Rooks in a Peaceful State (SDE 2, Phone Interview)

On the board, 1 is a rook and 0 is an empty cell. A rook can only move along its row or column to capture another rook it meets; it cannot jump over other rooks and cannot move to an empty cell. Keep capturing, and find the minimum number of rooks left once no two of them attack each other.

输入格式

The first line contains the number of rows n and the number of columns m, followed by n lines of m values, each 0 or 1. The original bounds are 1≤n,m≤1000, and a completely empty board is allowed.

输出格式

Output a single integer, the answer.

样例 1

输入：

2 3
1 0 1
1 0 0

输出：

1

样例 2

输入：

3 3
1 0 0
0 1 0
0 0 1

输出：

3

样例 3

输入：

1 1
0

输出：

0

样例说明

The outputs of the three public examples are 1; 3; and 0, checked by independent enumeration or direct simulation.