Description

A city is built on a regular $n \times m$ grid, where each cell is a $1 \times 1$ square. Each cell may contain a building, which is constructed from some number of $1 \times 1 \times 1$ cubes (that is, all building bases lie on the same plane). Several typical city models are shown below:

Now the height of the building on each grid cell is given, i.e., how many cubes are stacked on that cell. Determine the surface area of this city model.

Input Format

The first line contains 2 positive integers $n, m$, the length and width of the city model.

Then follow $n$ lines, each containing $m$ digit characters, describing the height of each cell (all building heights are greater than or equal to $0$ and less than or equal to $9$).

Output Format

A non-negative integer: the surface area of the city model.

3 3
111
212
111

38

3 4
1000
0010
0000

12

Hint

• 20% of the testdata satisfy: $n, m \leq 10$;
• 40% of the testdata satisfy: $n, m \leq 100$;
• 100% of the testdata satisfy: $1 \leq n, m \leq 1000$.

Translated by ChatGPT 5