题目描述
有一块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小块上的葡萄干数）
输出格式
只有一行，最小花费。
样例输入
样例输出
Error [ 更改语言 ] Language
讨论
