Greedy Algorithm

Time limit1sMemory limit512 MB

Summary

Given a torus grid of heights, add increments to whole rows and columns to maximize the number of adjacent cell pairs with equal height.

Level: Medium7 of 10
Topics: Matrix, Graph, Math
Solved: No attempts yet

Problem

I'm playing Super Mario Galaxy 3 (thanks for the copy, Nintendo). Most of the levels are small planets shaped like spheres, but bonus levels are different. They are shaped like a torus. You can imagine it as a rectangle with both pairs of opposite sides glued together. As a tribute to 8-bit predecessors, the surface of the planet is a small rectangular grid. Each cell in the grid has its own height. Playing the bonus level has two parts. In the first part, you can terraform the level by applying zero or more operations. In one operation, you choose a row or a column in the grid and increase the heights of all cells in that row or column by one. You can perform this operation any number of times, with the same or different rows and columns. After the terraforming, a coin appears at each common side of two cells of equal height, and you can collect them. You are good at platforming, so collecting all the coins is not a problem. Design an algorithm for terraforming the level so that the maximum possible number of coins appear. That is the problem for you.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n, m \le 50$ ), the dimensions of the rectangular grid. The next $n$ lines describe the initial heights of all cells. The $i$ -th of them contains $m$ integers $h_{i1}, h_{i2}, \ldots, h_{im}$ , where $h_{ij}$ is the height of the cell with coordinates $(i, j)$ . All the heights are between 0 and 500, inclusive. It is not required that this holds after the terraforming.

Output

Print a single integer, the maximum number of coins that can appear if you terraform the level optimally.

Hint

The level from the first example after an optimal terraforming:

Examples3

Example 1
Input
```
2 3
1 2 3
4 5 99
```
Expected output
```
8
```
Example 2
Input
```
3 3
3 2 4
2 2 3
5 4 6
```
Expected output
```
14
```

Example 3

Input

Expected output