시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 375 112 101 44.889%

문제

심술쟁이 해커 임준오(동탄 주민)는 새를 싫어한다. 특히 비둘기를 싫어한다.

준오는 수업시간에 옆자리 짝꿍과 빙고게임을 하기로 했다. 준오와 짝꿍은 각자 원하는 숫자를 n*m 격자의 빙고판에 적었다. 그러고는 서로의 빙고판을 교환했는데, 준오는 짝꿍의 빙고판을 확인하자마자 화가 치밀어 올랐다. 짝꿍의 빙고판에 9가 들어간 숫자들이 엄청 많아서 비둘기가 떠올랐기 때문이다. 그래서 준오는 짝꿍의 빙고판을 부숴버렸다.

하지만 준오의 폭동에는 특별한 룰이 있다. 바로 모든 행과 열을 통틀어서 9가 가장 많이 쓰여 있는 행 또는 열을 단 하나만 부수는 것이다!

빙고판을 부수는 순간 준오와 선생님의 눈이 마주쳤고, 선생님은 빙고판에 남아있는 9의 개수만큼 준오를 때리기로 했다. 준오는 몇 대를 맞아야할까?

입력

첫째 줄에 직사각형 빙고판의 크기를 뜻하는 n(1≤n≤500)과 m(1≤m≤500)이 주어진다. 다음 줄부터 n개의 줄에 걸쳐 각 줄마다 m개의 숫자들이 주어진다. 이는 크기가 n*m인 짝꿍의 빙고판의 상태를 나타내며, 빙고판에는 10,000 이하의 자연수들이 적힌다.

출력

준오가 몇 대 맞아야 하는지 출력한다.

예제 입력

3 4
1 2 3 9
4 5 9 6
9 7 8 9

예제 출력

2

예제 입력 2

4 4
11 12 19 14
99 39 14 90
13 47 81 99
32 72 29 66

예제 출력 2

4

힌트

첫 번째 예제에서, 3행 또는 4열을 부수면 2개의 9가 남고 준오는 총 2대를 맞는다.

두 번째 예제에서, 2행을 부수면 19, 99, 29가 남고 준오는 총 4대를 맞는다.