题目描述
有一块N*M的巧克力,需要将其分成1*1的小块。每次可以将一块巧克力用横向或纵向的切割线分为独立的两块。每一块1*1的巧克力上都有若干的葡萄干,每次切割一块巧克力的花费就是该巧克力上葡萄干的数目R_ij。给定每块1*1的巧克力上的葡萄干数,求花费最小的分割方案。
1<=N,M<=50
1<=R_ij<=1000
时限:5s
样例说明(许多种之一)
29+10+19+9+10=77
输入格式
第一行,N,M。
接下来有N行,每行M个数。第i+1行的第j个数就是题目描述中的R_ij(即位于第i行第j列的1*1小块上的葡萄干数)
输出格式
只有一行,最小花费。
样例输入
样例输出