시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 1 1 1 100.000%

문제

형택이는 보석상을 운영한다. 보석들은 NxM 형태로 배치되어 있는데, 각 행마다 보석들을 빛나게 해 줄 전등이 하나씩 총 N개 있고, 마찬가지로 각 행마다 전등이 하나씩 총 M개 있다.

각 보석은 일정 정도의 빛을 받아야 가장 아름다운 모양을 유지할 수 있는데, 이 정도는 각 보석마다 다르다. 예를 들어 아래는 2x3 형태로 배치된 보석들의 필요한 빛의 세기를 수치화해서 나타낸 것이다.

열전등1

열전등2

열전등3

행전등1

2

1

2

행전등2

3

1

1

(i, j)의 보석이 받는 빛의 세기는 행전등i의 빛의 세기와 열전등j의 빛의 세기의 합과 같다. 우리는 각 행전등과 열전등의 빛의 세기를 결정하려고 하는데, 적어도 주어진 빛의 세기만큼은 빛을 받도록 하고 싶다. 예를 들어 아래와 같이 빛의 세기를 결정했다고 하자.

2

0

1

1

3

1

2

1

3

1

2

각 칸에 써져 있는 숫자는 각 보석이 받게 되는 빛의 세기가 된다. 이렇게 되면 모든 보석들이 주어진 조건을 만족하게 되고, 또한 각 전등의 빛의 세기의 합인 2+0+1+1+1 = 5로 최소가 된다.

각 보석이 필요한 빛의 세기가 주어지면, 행전등과 열전등의 빛의 세기를 결정하여 조건을 만족하면서 전등들의 빛의 세기의 합을 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N, M이 주어진다. N, M은 256을 넘지 않는다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 보석이 필요한 빛의 세기를 나타내는 자연수가 각 줄마다 M개씩 주어진다. 주어지는 자연수는 2,000,000을 넘지 않는다.

출력

첫째 줄에 조건을 만족하는 빛의 세기의 총 합의 최소값을 출력한다.

예제 입력

2 3
2 1 2
3 1 1

예제 출력

5

힌트

출처

  • 문제를 번역한 사람: author5