Problem 1: Painting, (K Narayan Kumar, CMI)
A new university campus is coming up at Siruseri. At the centre of this campus is a piece of sculpture designed by a well known modern artist of Siruseri. The sculpture is made up of a set of concrete pillars of square cross-section of varying heights, placed next to each other.
The sculpture occupies a rectangular area of length M feet and width N feet. M × N pillars, each of cross section 1 foot by 1 foot, are placed in this area. These pillars of varying height. A description of such an sculpture can be given as an M × N array of numbers. The number at position (i,j) indicates the height of the pillar placed at position (i,j). For example, here is a description of a sculpture where M=2 and N=3.
3 2 3 2 1 1
The artist wants the entire sculpture to be painted in canary yellow. Notice that when two pillars are placed next to each other, a part of the surface of each of these pillars is no longer exposed to the outside and need not be painted. In the example above, only 9 square feet of the pillar at position (1,1) need to be painted. As a standalone pillar it has 13 square feet of paintable area (1 square foot on the top, and 3 square foot on each of its four faces). But, in the current arrangement, it is placed adjacent to two pillars which hide 2 square feet each of its exposed area. So, only 9 square feet need to be painted. If you add up the paintable areas for all the 6 pillars, you can see that a total of 34 square feet need to be painted.
Your task is to determine the total area that is to be painted given a description of the sculpture.
Input format
The first line of the input contains two integers, M and N, indicating the length and width of the sculpture in feet. This is followed by M rows of N positive numbers each. The jth number on line i+1 denotes height of the pillar at position (i,j).
Output format
A single positive integer indicating the total area to be painted.
Test data
You may assume 1 ≤ M,N ≤ 1000.
Example
We now illustrate the input and output formats using the example described above.
Sample input
2 3 3 2 3 2 1 1
Sample output
34