普罗夫迪夫著名的巧克力大师邦妮（Bonny）需要切割一块带有葡萄干的巧克力。这块巧克力是一个由若干相同的正方形小块组成的矩形。这些小块与巧克力的边缘对齐，排列成 $N$ 行 $M$ 列，总共 $N \times M$ 块。每一块上都有一个或多个葡萄干，且葡萄干不会位于小块之间或跨越小块。

最初，巧克力是一整块。邦妮需要将其切割成越来越小的块，直到最终将其切割成 $N \times M$ 个独立的小块。由于邦妮非常忙，她需要助手“狡猾的彼得”（Sly Peter）来帮忙切割。彼得只进行直线、贯穿式的切割，并且他要求为每一次切割支付报酬。邦妮手头没有钱，但她有很多剩余的葡萄干，所以她提出用葡萄干支付给彼得。彼得同意了这个安排，但条件是：每当他将一块给定的巧克力切割成两块较小的块时，他必须获得相当于该块巧克力上葡萄干总数的报酬。

邦妮希望支付给彼得的葡萄干尽可能少。她知道 $N \times M$ 个小块中每一块上的葡萄干数量。她可以决定将剩余的块交给彼得的顺序，也可以告诉彼得进行什么切割（水平或垂直）以及具体在哪里切割。请帮助邦妮决定如何将巧克力切割成独立的小块，以使她支付给彼得的葡萄干数量最少。

任务

编写一个程序，给定每一块小块上的葡萄干数量，确定邦妮必须支付给彼得的最少葡萄干数量。

数据范围

$1 \le N, M \le 50$：巧克力每一侧的小块数量。 $1 \le R_{k,p} \le 1000$：第 $k$ 行第 $p$ 列小块上的葡萄干数量。

输入格式

程序必须从标准输入读取以下数据： 第一行包含两个整数 $N$ 和 $M$，由单个空格分隔。 接下来的 $N$ 行描述了巧克力每一块上的葡萄干数量。其中第 $k$ 行描述了巧克力的第 $k$ 行。每一行包含 $M$ 个由空格分隔的整数。这些整数按从左到右的顺序描述了对应行上的小块。第 $k$ 行中的第 $p$ 个整数表示第 $k$ 行第 $p$ 列小块上的葡萄干数量。

输出格式

程序必须向标准输出写入一行，包含一个整数：邦妮支付给彼得的最少葡萄干数量。

子任务

对于总分 25 分的部分测试用例，$N$ 和 $M$ 不超过 7。

样例

输入格式 1

2 3
2 7 5
1 9 5

输出格式 1

77

说明

实现 77 这一成本的一种可能方式（共有多种方式）如下：

邦妮要求彼得做的第一次切割将第三列与巧克力的其余部分分离开来。邦妮需要为此支付 29 个葡萄干。

然后，邦妮将两个块中较小的一块交给彼得：即包含两块各有 5 个葡萄干的小块的那一块，并要求彼得将其切成两半，支付 10 个葡萄干。

此后，邦妮将剩余最大的块交给彼得：即包含葡萄干数量分别为 2、7、1 和 9 的小块的那一块。邦妮要求彼得进行水平切割，将第一行和第二行分开，并支付给他 19 个葡萄干。

随后，邦妮将左上角的块交给彼得，支付 9 个葡萄干。最后，邦妮要求彼得拆分左下角的块，支付 10 个葡萄干。

邦妮的总成本为 $29 + 10 + 19 + 9 + 10 = 77$ 个葡萄干。没有其他切割方案能以更低的成本将巧克力切割成 6 个小块。