건포도

플로브디브의 유명한 초콜릿 가공업자 Bonny는 가로 $M$칸, 세로 $N$칸의 격자로 이루어진 $N \times M$ 크기의 건포도 초콜릿을 만들었다. 각 $1 \times 1$ 칸에는 건포도가 최소 1개 이상 들어 있으며, 두 칸 이상에 걸쳐 있는 건포도는 없다.

처음에 초콜릿은 하나의 커다란 블록이며, Bonny는 이것을 $N \times M$개의 $1 \times 1$ 조각으로 모두 나누어야 한다. 이 일은 욕심쟁이 Peter가 맡는다. Peter는 한 번에 하나의 직사각형 조각을 가로 또는 세로 방향의 직선을 따라 두 조각으로 자를 수 있고, 자를 때마다 보상을 요구한다.

Bonny는 돈이 없어 건포도로 보상을 지불한다. Peter의 조건은 이렇다: 직사각형 조각 하나를 두 조각으로 자를 때마다, 자르기 직전 그 조각에 들어 있던 건포도의 총 개수만큼을 받는다. 어떤 조각을 어떤 위치에서 자를지는 모두 Bonny가 정할 수 있다.

각 칸에 들어 있는 건포도의 개수가 주어질 때, 모든 칸을 $1 \times 1$ 조각으로 나누기 위해 Bonny가 지불해야 하는 건포도 개수의 최솟값을 구하여라.

• 첫째 줄에 초콜릿의 크기 $N$과 $M$이 주어진다.
• 이어지는 $N$개의 줄에는 각각 $M$개의 정수 $R_{ij}$가 주어진다. $R_{ij}$는 $i$행 $j$열 칸에 들어 있는 건포도의 개수이다.
• $1 \le N, M \le 50$
• $1 \le R_{ij} \le 1000$

Bonny가 지불해야 하는 건포도 개수의 최솟값을 한 줄에 출력한다.

이 문제는 부분 직사각형에 대한 구간 동적 계획법으로 풀 수 있다. 한 직사각형 조각을 한 번 자르는 비용은 그 조각에 들어 있는 건포도의 총합이고, 잘린 두 조각은 서로 독립적으로 다시 나눌 수 있다. 따라서 크기가 작은 직사각형부터 '완전히 $1 \times 1$ 조각으로 나누는 최소 비용'을 차례로 채워 나가면 전체 답을 구할 수 있다.