网格

题目描述

给定一个 n × m 的非负整数网格 a，其中 a[i][j] 表示第 i 行第 j 列单元格的权值。

小红需要在网格中选择一整行和一整列，因此一共会选中 n + m - 1 个单元格（行列交点只计算一次），并希望这些单元格的权值之和尽可能大。

但是，在小红操作之前，小蓝可以任选一行，将这一整行的所有元素都进行一次“数位倒置”操作。数位倒置的定义如下：

• 将一个非负整数的十进制表示反转后重新写成一个数；
• 例如 123 倒置后得到 321；
• 100 倒置后得到 1；
• 9 倒置后仍然是 9。

小红会在小蓝操作后的网格上进行选择。

请你计算：经过小蓝选择某一行进行数位倒置后，小红最终最多可以得到多少权值和。

输入格式

第一行输入两个整数 n 和 m。

接下来输入 n 行，每行 m 个非负整数，表示网格 a。

输出格式

输出一个整数，表示小红最终最多可以得到的权值和。

数据范围

1 <= n, m <= 100

0 <= a[i][j] <= 10^6

样例 1

输入

2 3
12 5 7
3 40 6

输出

73

说明

如果小蓝将第一行倒置，网格变为：

21 5 7
3 40 6

此时小红选择第 1 行和第 2 列，可以得到：

21 + 5 + 7 + 40 = 73

若小蓝将第二行倒置，网格变为：

12 5 7
3 4 6

此时小红选择第 1 行和第 3 列，可以得到：

12 + 5 + 7 + 6 = 30

程序应当在所有“小蓝选一行倒置”与“小红选一行一列”的组合中取最大值。对该样例，最优结果为 73。