Indian National Olympiad in Informatics

Online Programming Contest, 4-5 June 2005

IARCS home > OLYMPIAD

Basic Division

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



Copyright (c) IARCS 2003-2018;   Last Updated: 05 Jul 2005