34621번 - 제설 작업

문제

겨울이 찾아와 하늘이네 부대 연병장에 눈이 쌓였다. 연병장은 $N \times M$ 크기의 격자로 나타낼 수 있으며, 각 칸 $(i, j)$에는 $A_{i,j}$ 만큼의 눈이 쌓여있다. 하늘이에게 주어진 임무는 제설 로봇을 이용해 연병장의 모든 눈을 치우는 것이다.

제설 로봇은 두 가지 종류의 작업을 여러 번 수행할 수 있다.

• 가로 제설: 특정 행 하나를 선택하여 그 행에 있는 모든 눈을 한 번에 제거한다.
• 세로 제설: 특정 열 하나를 선택하여 그 열에 있는 모든 눈을 한 번에 제거한다.

로봇의 성능은 정수 $P$로 표현된다. 어떤 작업을 수행하기 위해서는, 해당 작업으로 제거되는 눈의 총량이 로봇의 성능 $P$ 이하여야 한다. 예를 들어, $i$번째 행을 제설하려면 $i$번째 행에 쌓인 눈의 총합이 $P$보다 작거나 같아야 한다.

하늘이는 제설 작업을 완료하기 위해 필요한 로봇의 최소 성능이 궁금해졌다. 연병장의 모든 눈을 제거하기 위해 필요한 로봇의 최소 성능 $P$를 구하여라.

입력

첫째 줄에 연병장의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. (1ドル \le N, M \le 2,000$)

다음 $N$개의 줄에 걸쳐 $M$개의 정수가 공백으로 구분되어 주어진다. 이 중 $i$번째 줄의 $j$번째 정수는 칸 $(i, j)$에 쌓인 눈의 양 $A_{i,j}$를 의미한다. (1ドル \le A_{i,j} \le 500,000$)

출력

첫째 줄에 모든 눈을 제거하기 위해 필요한 로봇의 최소 성능 $P$를 출력한다.

제한

노트