만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

상자 속 딸기

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

요약
격자에 있는 딸기마다 행 누적합과 열 누적합의 쌍이 모두 다르도록 빈 칸에 추가할 딸기의 최소 개수를 구합니다.
난이도

보통10점 중 6점

유형
행렬, 누적 합, 그리디
정답자
아직 제출이 없습니다

문제

상자가 HH행 WW열 격자로 나뉘어 있다. 일부 칸에는 딸기가 들어 있다.

상자의 상태는 SS로 나타낸다. Sx,y=1S_{x,y} = 1이면 xx행 yy열 칸에 딸기가 하나 있고, Sx,y=0S_{x,y} = 0이면 그 칸은 비어 있다.

토모에는 딸기를 구별하기 위해 다음 방법을 고안했다.

  • Ax,yA_{x,y}는 i=xi = x이고 1≤j≤y1 \le j \le y인 모든 정수쌍 (i,j)(i,j)에 대한 Si,jS_{i,j}의 합이다.
  • Bx,yB_{x,y}는 1≤i≤x1 \le i \le x이고 j=yj = y인 모든 정수쌍 (i,j)(i,j)에 대한 Si,jS_{i,j}의 합이다.
  • xx행 yy열 칸에 딸기가 있으면, 그 딸기에 (Ax,y,Bx,y)(A_{x,y}, B_{x,y}) 튜플을 라벨로 붙인다.

이 방법으로는 서로 다른 딸기에 같은 라벨이 붙어 구별할 수 없게 될 수 있다. 그래서 토모에는 라벨을 붙이기 전에 딸기를 더 넣기로 했다.

더 정확히 말하면, Sx,y=0S_{x,y} = 0인 칸 (x,y)(x,y)마다 Sx,y←1S_{x,y} \leftarrow 1 연산을 0보다 큰 임의의 횟수만큼 실행했다.

모든 딸기에 서로 다른 라벨이 붙도록 하려면 최소 몇 개의 딸기를 추가해야 하는가?

입력

HH WW

S1,1S_{1,1} S1,2S_{1,2} …\dots S1,WS_{1,W}

S2,1S_{2,1} S2,2S_{2,2} …\dots S2,WS_{2,W}

⋮\vdots

SH,1S_{H,1} SH,2S_{H,2} …\dots SH,WS_{H,W}

출력

답을 한 줄에 출력한다. 출력의 끝에는 줄바꿈을 넣는다.

제한

  • 모든 입력은 정수이다.
  • 1≤H≤3001 \le H \le 300
  • 1≤W≤3001 \le W \le 300
  • 0≤Sx,y≤10 \le S_{x,y} \le 1

힌트

샘플 입력 1에서 토모에는 오른쪽 위 칸에 딸기를 하나 넣어 조건을 만족시킬 수 있다.

예제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