题目背景

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$。