미션 임파서블

화창한 봄날, 오랜 친구이자 예전 범행 동료인 패트릭을 만나러 간다. 패트릭은 프로그래밍 대회에 돈을 걸었다가 대부분을 잃었고, 한 건 더 해야 하는 처지가 되었다. 범죄에서 손을 뗀 나는 내키지 않지만, 계획을 들어 보기로 한다.

근처 창고에는 값비싼 부품 화물이 보관되어 있고, 패트릭은 그것을 최대한 많이 훔칠 생각이다. 건물에 침입하고, 경비원을 무력화하고, 레이저 경보망을 통과하는 일은 늘 하던 방식대로 처리한다. 문제는 창고 한복판에 설치된 보안 시스템이다. 패트릭은 이 장치를 끄지 못하고, 그래서 내 도움이 필요하다.

화물은 크기가 모두 같은 정육면체 상자에 담겨 있다. 상자는 가지런히 쌓여 $r$행 $c$열의 격자를 이룬다. 보안 시스템은 한 시간에 한 번 카메라 세 대로 사진을 찍는다. 정면 카메라는 각 열에서 가장 높은 더미의 높이를, 측면 카메라는 각 행에서 가장 높은 더미의 높이를 기록하고, 천장 카메라는 각 자리가 비었는지 아닌지를 기록한다. 세 사진 중 하나라도 달라지면 경보가 울린다.

다음 그림은 격자 하나와 각 카메라가 찍은 사진을 보여준다.

그림 C.1: 높이 격자와 각 카메라가 찍은 사진

패트릭은 창고에 들어가면 모든 더미의 높이를 재서 나에게 보낸다. 그다음 남은 상자를 같은 격자 위에 원하는 대로 다시 쌓을 수 있다. 다음번 사진 세 장이 지금과 똑같이 나오려면 아래 조건을 모두 지켜야 한다.

• 각 열에서 가장 높은 더미의 높이가 그대로여야 한다.
• 각 행에서 가장 높은 더미의 높이가 그대로여야 한다.
• 상자가 하나라도 있던 자리에는 상자가 하나 이상 남아 있어야 하고, 비어 있던 자리는 계속 비어 있어야 한다.

그림 C.1의 격자에서는 상자 9개를 훔칠 수 있다. 다음 그림은 보안 시스템이 보기에 이전과 똑같은, 도난 이후의 배치 하나이다.

그림 C.2: 도난 이후 가능한 높이 격자

세 조건을 모두 지키면서 패트릭이 가져갈 수 있는 상자의 최대 개수를 구하라.

첫째 줄에 격자의 행 수 $r$과 열 수 $c$가 주어진다 ($1 \le r \le 100$, $1 \le c \le 100$).

다음 $r$개 줄에는 줄마다 $c$개의 정수가 주어지며, 그 행에 놓인 더미의 높이를 상자 개수로 나타낸다. 모든 높이는 $0$ 이상 $10^9$ 이하이다.

경보를 울리지 않고 훔칠 수 있는 상자의 최대 개수를 출력한다.