← 返回题目列表

Codeforces · 1219/G

G. 收割机

中文机器翻译题面 查看原题

现在是泡泡杯决赛赛季,农民约翰尼·巴布斯必须收获他的泡泡。气泡位于由 $$$N$$$ x $$$M$$$ 方形地块组成的矩形气泡场中,分为 $$$N$$$ 行和 $$$M$$$ 列。 $$$i^{th}$$$ 行和 $$$j^{th}$$$ 列中的地块产生 $$$A_{i,j}$$$ 气泡。

Johnny Bubbles 提供了一种非常特殊的自动驾驶气泡收集器,一旦手动放置在行或列的开头,就会自动收集该行或列中的所有气泡。一旦收割机到达行或列的末端,它就会停止并必须重新定位。收割机可以多次穿过任何包裹,但它只能从包裹中收集一次气泡。

Johnny 是一位非常忙碌的农民,因此他每天最多可以手动定位收割机四次。约翰尼也没有耐心,所以他想在第一天收获尽可能多的泡泡。

请帮助约翰尼计算他第一天最多可以收集多少个泡泡。

输入

第一行包含两个整数 $$$N$$$ 和 $$$M$$$ ($$$1$$$ $$$\leq$$$ $$$N$$$, $$$M$$$$$\leq$$$ $$$N$$$ * $$$M$$$ $$$\leq$$$ $$$10^{5}$$$) - 气泡域大小。

接下来的 $$$N$$$ 行包含 $$$M$$$ 整数。 $$$i^{th}$$$ 行中的 $$$j^{th}$$$ 元素为 $$$A_{i,j}$$$ ($$$0$$$ $$$\leq$$$ $$$a_{i,j}$$$ $$$\leq$$$ $$$10^{9}$$$) — 位于 $$$i^{th}$$$ 行和$$$j^{th}$$$ 列。

输出

输出包含一个整数 - 约翰尼在第一天可以收获的最大气泡数。

示例

输入 #1

2 2
1 2
3 4

输出 #1

10

输入 #2

5 5
0 9 2 7 0
9 0 3 0 5
0 8 0 3 1
6 7 4 3 9
3 6 4 1 0

输出 #2

80

注意

在第一个示例中,农民约翰尼可以通过将收割机放置在第一行和第二行来收割所有气泡。

在第二个示例中,Johnny 收集最大数量气泡的一种方法是将收集器放置在第二行、第四行、第二列和第四列。