n×m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a+1)×(b+1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다.

위 그림 1과 같은 6×7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다. 분할의 '점수' 는 잘라진 각 부분의 합들 중에서 가장 큰 값으로 정의한다. 예를 들어, 그림 2와 같은 분할에서의 점수는 색칠한 부분의 합인 19이다. 한편, 그림 3과 같이 행렬을 분할하면 점수는 15로 최소가 된다. 행렬이 주어졌을 때 가능한 최소 점수를 구하는 프로그램을 작성하시오.

#1579 upload 5 done 3 how_to_reg 3

행렬 분할 timer 1s memory 64MB

#1579

행렬 분할 1s 64MB