시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB411100.000%

문제

A box is divided into grids with $H$ rows and $W$ columns. Some squares contain strawberries.

The state of the box is denoted by $S$, and $S_{x,y} = 1$ means that the square in the $x$-th row and $y$-th column contains one strawberry. If $S_{x,y} = 0$, the square in the $x$-th row and $y$-th column is empty.

Tomoe devised the following method to distinguish between these strawberries.

  • Let $A_{x,y}$ be defined as the sum of $S_{i,j}$ for all integer pairs $(i,j)$ satisfying $i = x$, $1 \le j \le y$.
  • Let $B_{x,y}$ be defined as the sum of $S_{i,j}$ for all integer pairs $(i,j)$ satisfying $1 \le i \le x$, $j = y$.
  • If the square in the $x$-th row and $y$-th column contains a strawberry, label the strawberry with the tuple $(A_{x,y}, B_{x,y})$.

This method could result in multiple strawberries having the same label, and the strawberries could not be distinguished. Therefore, she decided to add some strawberries before labeling them.

More formally, for $(x,y)$ such that $S_{x,y} = 0$, we operated $S_{x,y} \leftarrow 1$ any number of times greater than $0$.

What is the minimum number of strawberries that must be added to label all the strawberries differently?

입력

$H$ $W$

$S_{1,1}$ $S_{1,2}$ $\dots$ $S_{1,W}$

$S_{2,1}$ $S_{2,2}$ $\dots$ $S_{2,W}$

$\vdots$

$S_{H,1}$ $S_{H,2}$ $\dots$ $S_{H,W}$

출력

Output the answer in one line. Add a new line at the end of the output.

제한

  • All inputs consist of integers.
  • $1 \le H \le 300$
  • $1 \le W \le 300$
  • $0 \le S_{x,y} \le 1$

예제 입력 1

3 2
1 0
0 1
0 1

예제 출력 1

1

예제 입력 2

4 4
0 1 1 1
1 1 1 0
1 0 1 1
1 0 1 0

예제 출력 2

2

예제 입력 3

5 5
0 0 1 0 1
0 1 0 1 0
0 0 1 0 1
0 1 0 1 0
0 0 1 0 1

예제 출력 3

8

예제 입력 4

1 1
0

예제 출력 4

0

힌트

In Sample Input 1, Tomoe can achieve the condition by placing a strawberry in the upper right square.