Fraises dans une boîte

시간 제한4초메모리 제한1024 MB

요약
이진 격자에 딸기를 최소한으로 추가해 모든 1 칸이 서로 다른 (행 누적, 열 누적) 쌍을 갖도록 만든다.
난이도

보통10점 중 7점

유형
그리디, 동적 계획법
정답자
아직 제출이 없습니다

문제

A box is divided into grids with HH rows and WW columns. Some squares contain strawberries.

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

Tomoe devised the following method to distinguish between these strawberries.

  • Let A_x,yA\_{x,y} be defined as the sum of S_i,jS\_{i,j} for all integer pairs (i,j)(i,j) satisfying i=xi = x, 1≤j≤y1 \le j \le y.
  • Let B_x,yB\_{x,y} be defined as the sum of S_i,jS\_{i,j} for all integer pairs (i,j)(i,j) satisfying 1≤i≤x1 \le i \le x, j=yj = y.
  • If the square in the xx-th row and yy-th column contains a strawberry, label the strawberry with the tuple (A_x,y,B_x,y)(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)(x,y) such that S_x,y=0S\_{x,y} = 0, we operated S_x,y←1S\_{x,y} \leftarrow 1 any number of times greater than 00.

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

입력

HH WW

S_1,1S\_{1,1} S_1,2S\_{1,2} …\dots S_1,WS\_{1,W}

S_2,1S\_{2,1} S_2,2S\_{2,2} …\dots S_2,WS\_{2,W}

⋮\vdots

S_H,1S\_{H,1} S_H,2S\_{H,2} …\dots S_H,WS\_{H,W}

출력

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

제한

  • All inputs consist of integers.
  • 1≤H≤3001 \le H \le 300
  • 1≤W≤3001 \le W \le 300
  • 0≤S_x,y≤10 \le S\_{x,y} \le 1

힌트

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

예제4

  1. 예제 1

    입력
    3 2
    1 0
    0 1
    0 1
    
    예상 출력
    1
    
  2. 예제 2

    입력
    4 4
    0 1 1 1
    1 1 1 0
    1 0 1 1
    1 0 1 0
    
    예상 출력
    2
    
  3. 예제 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
    
    예상 출력
    8
    
  4. 예제 4

    입력
    1 1
    0
    
    예상 출력
    0