You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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 的最少的葡萄干的数目。

2 3
2 7 5
1 9 5

77

提示

样例解释

一种可能的代价为 $77$ 的切割方案如下所示：

第一次切割将第三列和剩下来的巧克力分开了。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$。