[IOI2009] Raisins
题目背景
IOI2009 D1T4
题目描述
普罗夫迪夫的著名巧克力大师 Bonny 需要切开一板带有葡萄干的巧克力。巧克力是一个包含许多相同的方形小块的矩形。小块沿着巧克力的边排列成 $N$ 行 $M$ 列,共有 $N\times M$ 块。每个小块上有 $1$ 个或多个葡萄干,没有葡萄干在小块的边上或者跨过两个小块。
最开始,巧克力是一整块。Bonny 需要把它切成上述的 $N\times M$ 个独立的小块。因为 Bonny 很忙,她需要她的助手 Sly Peter 帮她切。
Peter 只能从一端到另一端切直线,并且他要为他的每一刀得到报酬。Bonny 手头没有钱,但是她有足够的葡萄干,所以她提出用葡萄干付给 Peter。Sly Peter 同意接受葡萄干,但是有下面的条件:每次他把给定的一块巧克力切成两小块,他都要得到和那块给定的巧克力上葡萄干数目相同的葡萄干。
Bonny 想要付给 Peter 尽可能少的葡萄干。她知道这 $n\times m$ 个小块中每一个小块上葡萄干的数目。她可以选择递给 Peter 的巧克力的顺序,也可以告诉 Peter 如何切(横切还是竖切)以及从哪里切。请告诉 Bonny 如何把巧克力切成一个个独立的小块,使她能够付给 Sly Peter 尽可能少的葡萄干。
**任务**:编写一个程序,给定每个小块上葡萄干的数目,计算出 Bonny 要付给 Sly Peter 的最少的葡萄干的数目。
输入输出格式
输入格式
第一行两个由空格隔开的整数 $N, M$,分别表示巧克力的行数和列数。
接下来 $N$ 行描述了每个小块上葡萄干的数目。其中第 $k$ 行描述了第 $k$ 行小块的巧克力。每行包含 $m$ 个整数,分别以一个空格隔开。这些整数描述了该行从左到右的小块。第 $k$ 行的第 $p$ 个整数表示位于第 $k$ 行第 $p$ 列的小块上的葡萄干数目 $R_{k, p}$。
输出格式
一行一个整数,表示 Bonny 要付给 Sly Peter 的最少的葡萄干的数目。
输入输出样例
输入样例 #1
2 3
2 7 5
1 9 5
输出样例 #1
77
说明
### 样例解释
一种可能的代价为 $77$ 的切割方案如下所示:
![](https://cdn.luogu.com.cn/upload/image_hosting/zg74ypip.png)
第一次切割将第三列和剩下来的巧克力分开了。Bonny 需要付给 Peter $29$ 个葡萄干。
接下来 Bonny 把较小的那一块巧克力(有两小块,每一块都有 $5$ 个葡萄干)给 Peter,要求 Peter 切成两半并支付 $10$ 个葡萄干。
在此之后,Bonny 给 Peter 剩下来的最大块(分别有 $2, 7, 1, 9$ 个葡萄干在它的四个小块上)。Bonny 要求 Peter 水平切割这一块,将第一行和第二行分开并付给他 $19$ 个葡萄干。
此后 Bonny 给 Peter 左上角的块,支付 $9$ 个葡萄干。最后 Bonny 要求 Peter 将左下角的块分开,支付 $10$ 个葡萄干。
Bonny 的总代价是 $29 + 10 + 19 + 9 + 10 = 77$ 个葡萄干。没有其它安排切割的方案有更小的代价。
### 数据范围与约定
- 对于 $25\%$ 的数据,$n,m\leq 7$。
- 对于 $100\%$ 的数据,$1\leq n,m\leq 50$,$1\leq R_{k, p}\leq 1000$。