CF1219G Harvester

现在正值 Bubble Cup 决赛季，农夫 Johnny Bubbles 必须收获他的泡泡。这些泡泡分布在一个由 $N \times M$ 个方格组成的矩形泡泡田中，共有 $N$ 行 $M$ 列。第 $i$ 行第 $j$ 列的地块能产出 $A_{i,j}$ 个泡泡。 Johnny Bubbles 有一台非常特殊的自动驾驶泡泡收割机，每次只需手动将其放置在某一行或某一列的起点，它就会自动收割该行或该列的所有泡泡。当收割机到达该行或该列的末端后会停止，需要重新手动放置。收割机可以多次经过同一个地块，但每个地块的泡泡只能被收割一次。 Johnny 非常忙碌，所以每天最多只能手动放置收割机 4 次。同时他也很急切，希望第一天能收获尽可能多的泡泡。 请你帮助 Johnny 计算第一天最多能收获多少个泡泡。

第一行包含两个整数 $N$ 和 $M$（$1 \leq N, M \leq N \times M \leq 10^{5}$），表示泡泡田的大小。 接下来的 $N$ 行，每行包含 $M$ 个整数。第 $i$ 行第 $j$ 个元素为 $A_{i,j}$（$0 \leq a_{i,j} \leq 10^{9}$），表示第 $i$ 行第 $j$ 列地块的泡泡产量。

输出一个整数，表示 Johnny 第一天最多能收获的泡泡数量。

在第一个样例中，Johnny 可以通过将收割机分别放在第一行和第二行，收割所有泡泡。 在第二个样例中，一种收割最多泡泡的方法是将收割机分别放在第二行、第四行、第二列和第四列。 由 ChatGPT 4.1 翻译