18495번 - Greedy Algorithm 다국어

I’m playing Super Mario Galaxy 3 (thanks for the copy, Nintendo). Most of the levels are small planets in a shape of sphere, but bonus levels are something different. They are in a shape of torus. You can imagine it as 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 consists of two parts. In the first part I can terraform the level by applying zero or more operations. In one operation I choose a row or a column in the grid, and increase the heights of all the cells in that row or column by one. I can perform this operation any number of times with same or different rows and columns.

After the terraforming a coin appears at each common side of two cells of equal height, and I can collect them. I’m good at platforming, so collecting all the coins is not a problem. Designing algorithm for terraforming the level so that the maximum possible number of coins appear — that’s the problem. The problem for you, actually.

The first line contains two integers n and m (2 ≤ n, m ≤ 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, . . . , h_im, where h_ij denotes 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.

Print a single integer — the maximum number of coins can appear if I terraform the level optimally.

The level from the first example after an optimal terraforming: