{"raw_statement":[{"iden":"statement","content":"A city is built on the top of a rectangular n × m grid where all the grid cells are equal squares. Each of the n·m grid cells can serve as a foundation of a single building in the city. A building is represented as a number of 1 × 1 × 1 cubes stacked on the top of each other. The cube that lays in the foundation of a building entirely occupies a single cell on the grid. It is clear that adjacent buildings can share a wall or a part of it. Typical cities can be seen on the image below.\n\nThe King of Berland has a 3D model of the capital city in his office. This model was made on a special 3D-printer out of plastic. It represents a layout of the capital city, but the scale is smaller, so it's very convenient for the King to examine the model without having to visit the city itself. The King is bored though because the model is colorless, so he wants to paint the model. To calculate the exact amount of required paint he should know the total area of the model's surface.\n\nYou have to help the King and write a program that will calculate the required surface area of the given model. While calculating the surface area you should count not only the side surfaces, but also the areas of the top and bottom facets.\n\nThe model is given to you as n × m matrix of digits. A digit in the j-th position of the i-th row stands for the height of the building with its foundation in cell (i, j) of the model. If the corresponding digit is equal to \"_0_\", it means there is no building built on the top of this cell.\n\nThe first line of input contains a pair of integers n, m (1 ≤ n, m ≤ 100), where n — amount of rows in the given grid, m — amount of columns. The following n lines contain the description of the model. These n lines contain m digits each representing heights of the buildings. It's guaranteed that the given matrix contains at least one non-zero digit.\n\nOutput the only positive integer — surface area of the model.\n\nThe first sample test corresponds to the leftmost picture from the problem statement.\n\n"},{"iden":"input","content":"The first line of input contains a pair of integers n, m (1 ≤ n, m ≤ 100), where n — amount of rows in the given grid, m — amount of columns. The following n lines contain the description of the model. These n lines contain m digits each representing heights of the buildings. It's guaranteed that the given matrix contains at least one non-zero digit."},{"iden":"output","content":"Output the only positive integer — surface area of the model."},{"iden":"examples","content":"Input3 3111212111Output38Input3 4100000100000Output12"},{"iden":"note","content":"The first sample test corresponds to the leftmost picture from the problem statement."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid, with $ 1 \\leq n, m \\leq 100 $.  \nLet $ H = (h_{i,j})_{i=1,\\dots,n; j=1,\\dots,m} $ be an $ n \\times m $ matrix of non-negative integers, where $ h_{i,j} $ represents the height of the building at cell $ (i,j) $.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 100 $  \n2. $ h_{i,j} \\in \\mathbb{Z}_{\\geq 0} $ for all $ i,j $  \n3. $ \\exists\\ (i,j) $ such that $ h_{i,j} > 0 $\n\n**Objective**  \nCompute the total surface area $ S $ of the 3D model, defined as the sum of:  \n- The top and bottom faces of all cubes: $ 2 \\cdot \\sum_{i=1}^n \\sum_{j=1}^m [h_{i,j} > 0] $  \n- The lateral (side) faces exposed to air or adjacent lower buildings:  \n\nFor each cell $ (i,j) $, the exposed side area is the sum over its 4 orthogonal neighbors $ (i',j') \\in \\{(i-1,j), (i+1,j), (i,j-1), (i,j+1)\\} $ of:  \n$$\n\\max(0, h_{i,j} - h_{i',j'})\n$$  \nplus the exposed sides on the grid boundaries (i.e., if a neighbor is out of bounds, contribute $ h_{i,j} $).\n\nThus, total surface area:  \n$$\nS = 2 \\cdot \\sum_{i=1}^n \\sum_{j=1}^m \\mathbf{1}_{h_{i,j} > 0} + \\sum_{i=1}^n \\sum_{j=1}^m \\sum_{(i',j') \\in \\mathcal{N}(i,j)} \\max(0, h_{i,j} - h_{i',j'})\n$$  \nwhere $ \\mathcal{N}(i,j) $ is the set of 4 orthogonal neighbors within bounds, and $ h_{i',j'} = 0 $ if $ (i',j') $ is out of bounds.","simple_statement":"You are given an n×m grid where each cell has a building with a certain height (0 means no building). Each building is made of 1×1×1 cubes stacked vertically. Calculate the total surface area of the entire model, including top, bottom, and all side faces. Adjacent buildings share walls, so shared faces are not counted.","has_page_source":false}