상자 속 딸기
시간 제한4초메모리 제한1024 MB
격자에 있는 딸기마다 행 누적합과 열 누적합의 쌍이 모두 다르도록 빈 칸에 추가할 딸기의 최소 개수를 구합니다.
문제
상자가 행 열 격자로 나뉘어 있다. 일부 칸에는 딸기가 들어 있다.
상자의 상태는 로 나타낸다. 이면 행 열 칸에 딸기가 하나 있고, 이면 그 칸은 비어 있다.
토모에는 딸기를 구별하기 위해 다음 방법을 고안했다.
- 는 이고 인 모든 정수쌍 에 대한 의 합이다.
- 는 이고 인 모든 정수쌍 에 대한 의 합이다.
- 행 열 칸에 딸기가 있으면, 그 딸기에 튜플을 라벨로 붙인다.
이 방법으로는 서로 다른 딸기에 같은 라벨이 붙어 구별할 수 없게 될 수 있다. 그래서 토모에는 라벨을 붙이기 전에 딸기를 더 넣기로 했다.
더 정확히 말하면, 인 칸 마다 연산을 0보다 큰 임의의 횟수만큼 실행했다.
모든 딸기에 서로 다른 라벨이 붙도록 하려면 최소 몇 개의 딸기를 추가해야 하는가?
입력
출력
답을 한 줄에 출력한다. 출력의 끝에는 줄바꿈을 넣는다.
제한
- 모든 입력은 정수이다.
힌트
샘플 입력 1에서 토모에는 오른쪽 위 칸에 딸기를 하나 넣어 조건을 만족시킬 수 있다.